【题目描述】
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
【示例1】
输入: "()"
输出: true
【示例2】
输入: "()[]{}"
输出: true
【示例3】
输入: "(]"
输出: false
【示例4】
输入: "([)]"
输出: false
【示例5】
输入: "{[]}"
输出: true
【思路1】
1、使用库函数
2、使用空串替换 () [] {}任意出现的字符对
3、如果最后字符串长度为0，那么返回true 否则返回false
4、时间复杂度O(n^2)，时间比较差
Swift代码实现：
func isValid(_ s: String) -> Bool {
if s.count == 0 { return true }
var tmp = s
while tmp.contains("()") || tmp.contains("{}") || tmp.contains("[]") {
tmp = tmp.replacingOccurrences(of: "()", with: "")
tmp = tmp.replacingOccurrences(of: "{}", with: "")
tmp = tmp.replacingOccurrences(of: "[]", with: "")
}
return tmp.count == 0
}
【思路2】
1、使用栈或者数组
2、如果是左括号( { [，装进数组或进栈
3、如果是右括号) } ]，判断指针index 如果小于等于0 返回false ，因为第一个就是右括号) } ]，如果index大于0，判断当前字符和数组最后一个字符或栈顶字符是否是左括号( { [，如果是删除数组最后一个字符或pop栈顶元素；index--；
4、遍历s完成后 判断栈或数组是否为空，为空返回true 否则返回false
5、时间复杂度O(n)
6、空间复杂度O(n)
Swift代码实现：
func isValid(_ s: String) -> Bool {
if s.count == 0 { return true }
var chaArr = [Character]()
var index = 0
for c in s {
if c == "(" || c == "{" || c == "[" {
chaArr.append(c)
index+=1
} else {
if index <= 0 {
return false
}
let tmp = (c == ")" && chaArr[index-1] == "(") || (c == "]" && chaArr[index-1] == "[") || (c == "}" && chaArr[index-1] == "{")
if tmp {
chaArr.removeLast()
}
index-=1
}
}
return chaArr.count == 0
}
