Valid Parentheses solution using TypeScript
Below is my TypeScript solution to the LeetCode "Valid Parentheses" question.
Time Complexity: Because each character in the string will be visited one time, the time complexity is O(n), where n represents the length of the string.
Space Complexity: This approach will place n elements in the stack in the worst case, making the space complexity O(n).
/**
* Given a string containing just the characters
* '(', ')', '{', '}', '[' and ']', determine if the
* input string is valid.
*
* Time Complexity: O(n)
* Space Complexity: O(n)
*
* Input: "{[]}"
* Output: true
*/
function isValid(s: string): boolean {
const stack = [];
const map = new Map([
['}', '{'],
[']', '['],
[')', '(']
])
const openingBraces = Array.from(map.values());
let mismatchedBrace = false;
for (let i = 0; i < s.length; i++) {
if (openingBraces.includes(s[i])) {
stack.push(s[i]);
} else {
const openingBrace = stack.pop();
const expectedBrace = map.get(s[i]);
if (openingBrace !== expectedBrace) {
mismatchedBrace = true;
break;
}
}
}
return !mismatchedBrace && !stack.length;
}