20. 有效的括号
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
方法一 栈+hash表
配对的问题首先想到的是用栈来解决，但是如何巧妙的使用hash表刚开始没想到，用的是if判断。
由于要配对，考虑以下几种情况：
1.数据自身不成对，奇数个时结果必然无法配对
2.按顺序入栈，配对到出栈，最后栈为空即为所有配对完成
Swift
func isValid(_ s: String) -> Bool {
//为奇数则不可能配对，直接返回
if s.count % 2 != 0 {
return false
}
let hashTable:[Character : Character] = [
"}" : "{",
")" : "(",
"]" : "["
]
//create stack
let stack = Stack()
for char in s {
if hashTable.keys.contains(char) {
if stack.top() == hashTable[char] {
let _ = stack.pop()
continue
}else {
return false
}
}
stack.push(char)
}
let result = stack.count() == 0 ? true : false
return result
}
其中栈代码如下：
class Stack {
private var items = [Character]()
func push(_ chara: Character) {
items.append(chara)
}
func pop() -> Character? {
if items.count <= 0 {
return nil
}
let res = items.last
items.removeLast()
return res
}
func top() -> Character? {
return items.last
}
func count() -> Int {
return items.count
}
}
OC
-(BOOL)isValid:(NSString *)s {
if (s.length % 2 != 0) {
return NO;
}
NSDictionary *hashTable = @{
@")" : @"(",
@"}" : @"{",
@"]" : @"["
};
Stack *stack = [Stack new];
for (NSInteger i=0; i<s.length; i++) {
unichar chara = [s characterAtIndex:i];
NSString *s = [[NSString alloc] initWithCharacters:&chara length:1];
if ([hashTable.allKeys containsObject:s]) {
if ([stack.top isEqualToString:hashTable[s]]) {
[stack pop];
continue;
}else {
return NO;
}
}
[stack push:s];
}
return stack.count == 0 ? YES : NO;
}
实现栈结构的OC代码：
@interface Stack<T> : NSObject
- (void)push:(T)item;
- (T)pop;
- (T)top;
-(NSInteger)count;
@end
//------------------------------------------
@implementation Stack
- (instancetype)init {
if (self = [super init]) {
_items = [[NSMutableArray alloc] init];
}
return self;
}
- (void)push:(id)item {
[self.items addObject:item];
}
- (id)pop {
id last = _items.lastObject;
[self.items removeLastObject];
return last;
}
- (id)top {
return _items.lastObject;
}
-(NSInteger)count {
return self.items.count;
}
@end
