Valid Parentheses

The Problem 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 closing bracket has a corresponding open bracket of the same type. Examples Input: s = "()" Output: true Input: s = "()[]{}" Output: true Input: s = "(]" Output: false Input: s = "([])" Output: true Constraints 1 <= s.length <= 10⁴ s consists of parentheses only '()[]{}'. Brute Force Solution func isValid(_ s: String) -> Bool { var s = s while s.contains("()") || s.contains("{}") || s.contains("[]") { s = s.replacingOccurrences(of: "()", with: "") s = s.replacingOccurrences(of: "{}", with: "") s = s.replacingOccurrences(of: "[]", with: "") } return s.isEmpty } Explanation The brute force way to solve this problem is to check if the string contains "()", "{}", "[]" and replace them with an empty string. It’s not a very efficient algorithm and takes O(n²) time because of the while loop and the replacing operation on the entire string. We can optimize it by using a stack data structure. ...