Description:
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Examples:
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: falseSolution in Python:
To solve this problem, we need to ensure that every opening bracket has a corresponding and correctly ordered closing bracket. We can use a stack data structure to achieve this. The stack allows us to keep track of the brackets as they appear and to check them in the correct order when we encounter a closing bracket.
Step-by-step approach:
- Initialization: Create a stack to keep track of opening brackets. Also, use a dictionary to map each closing bracket to its corresponding opening bracket.
- Iterate through the string: For each character in the string:
- If it is an opening bracket, push it onto the stack.
- If it is a closing bracket, check if the stack is empty or if the top of the stack is not the corresponding opening bracket. If either is true, the string is not valid.
- If the top of the stack matches the corresponding opening bracket, pop the stack.
- Final check: After processing all characters, if the stack is empty, all brackets were properly closed and nested. If not, the string is not valid.
Python
class Solution:
def isValid(self, s: str) -> bool:
# Dictionary to hold the mappings of closing brackets to their respective opening brackets
bracket_map = {')': '(', '}': '{', ']': '['}
# Stack to keep track of the opening brackets
stack = []
# Iterate through each character in the string
for char in s:
# If the character is a closing bracket
if char in bracket_map:
# Pop the top element from the stack if it's not empty; otherwise assign a dummy value
top_element = stack.pop() if stack else '#'
# Check if the top element of the stack is the matching opening bracket
if bracket_map[char] != top_element:
return False
else:
# If it's an opening bracket, push it onto the stack
stack.append(char)
# If the stack is empty at the end, all the brackets were properly closed
return not stack
# Example usage
sol = Solution()
print(sol.isValid("()")) # Output: true
print(sol.isValid("()[]{}")) # Output: true
print(sol.isValid("(]")) # Output: false
print(sol.isValid("([)]")) # Output: false
print(sol.isValid("{[]}")) # Output: trueExplanation of the Code:
- bracket_map: This dictionary helps to quickly find the matching opening bracket for any closing bracket.
- stack: This list is used as a stack to keep track of the unmatched opening brackets.
- Iterating through the string:
- If the character is a closing bracket (i.e., it exists in
bracket_map), we check if the stack is not empty and if the top of the stack is the correct matching opening bracket. - If it’s an opening bracket, we simply push it onto the stack.
- If the character is a closing bracket (i.e., it exists in
- Final return: After processing the string, if the stack is empty, it means every opening bracket had a corresponding closing bracket in the correct order, and the string is valid. If not, the string is invalid.
This solution efficiently checks for the validity of the bracket sequence using a stack and runs in O(n) time complexity, where n is the length of the input string.
Solution in Javascript:
JavaScript
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
// Mapping of closing brackets to their corresponding opening brackets
const bracketMap = {
')': '(',
'}': '{',
']': '['
};
// Stack to keep track of opening brackets
const stack = [];
// Iterate through each character in the string
for (let char of s) {
// If the character is a closing bracket
if (bracketMap[char]) {
// Pop the top element from the stack if it's not empty; otherwise assign a dummy value
const topElement = stack.length > 0 ? stack.pop() : '#';
// Check if the top element of the stack is the matching opening bracket
if (bracketMap[char] !== topElement) {
return false;
}
} else {
// If it's an opening bracket, push it onto the stack
stack.push(char);
}
}
// If the stack is empty at the end, all the brackets were properly closed
return stack.length === 0;
};
// Example usage
console.log(isValid("()")); // Output: true
console.log(isValid("()[]{}")); // Output: true
console.log(isValid("(]")); // Output: false
console.log(isValid("([)]")); // Output: false
console.log(isValid("{[]}")); // Output: trueSolution in Java:
Java
import java.util.HashMap;
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
// HashMap to store the mappings of closing brackets to opening brackets
HashMap<Character, Character> bracketMap = new HashMap<>();
bracketMap.put(')', '(');
bracketMap.put('}', '{');
bracketMap.put(']', '[');
// Stack to keep track of opening brackets
Stack<Character> stack = new Stack<>();
// Iterate through each character in the string
for (char ch : s.toCharArray()) {
// If the character is a closing bracket
if (bracketMap.containsKey(ch)) {
// Pop the top element from the stack if it's not empty; otherwise assign a dummy value
char topElement = stack.isEmpty() ? '#' : stack.pop();
// Check if the top element of the stack is the matching opening bracket
if (topElement != bracketMap.get(ch)) {
return false;
}
} else {
// If it's an opening bracket, push it onto the stack
stack.push(ch);
}
}
// If the stack is empty at the end, all the brackets were properly closed
return stack.isEmpty();
}
// Example usage
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.isValid("()")); // Output: true
System.out.println(sol.isValid("()[]{}")); // Output: true
System.out.println(sol.isValid("(]")); // Output: false
System.out.println(sol.isValid("([)]")); // Output: false
System.out.println(sol.isValid("{[]}")); // Output: true
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public bool IsValid(string s) {
// Dictionary to store the mappings of closing brackets to opening brackets
Dictionary<char, char> bracketMap = new Dictionary<char, char> {
{')', '('},
{'}', '{'},
{']', '['}
};
// Stack to keep track of opening brackets
Stack<char> stack = new Stack<char>();
// Iterate through each character in the string
foreach (char ch in s) {
// If the character is a closing bracket
if (bracketMap.ContainsKey(ch)) {
// Pop the top element from the stack if it's not empty; otherwise assign a dummy value
char topElement = stack.Count > 0 ? stack.Pop() : '#';
// Check if the top element of the stack is the matching opening bracket
if (topElement != bracketMap[ch]) {
return false;
}
} else {
// If it's an opening bracket, push it onto the stack
stack.Push(ch);
}
}
// If the stack is empty at the end, all the brackets were properly closed
return stack.Count == 0;
}
}