leetcode-20.有效的括号(OC)

20. 有效的括号

地址:https://leetcode-cn.com/problems/valid-parentheses/

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：
输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false
示例 4：

输入：s = "([)]"
输出：false
示例 5：

输入：s = "{[]}"
输出：true

方法1 特殊字符串替换法

不能使用(){}[]替换 因为顺序不同
肯定是考虑 遍历

字符串中包含(){}[] 就将(){}[]替换为空 最后不是空字符串 就是false

上代码

while ([str containsString:@"{}"] || [str containsString:@"()"] || [str containsString:@"[]"]) {
        str = [str stringByReplacingOccurrencesOfString:@"{}" withString:@""];
        str = [str stringByReplacingOccurrencesOfString:@"()" withString:@""];
        str = [str stringByReplacingOccurrencesOfString:@"[]" withString:@""];
    }
    
    return str.length == 0;

方法2 使用栈的思想

1.首先有效括号一定是相同类型左右闭合, 即偶数, 所以奇数先排除
2.将（）放到字典中，方便匹配
3.for循环判断, 左括号依次入栈
4.右括号时需要先判断是否是否为空，如果是空数组就表示没有左括号 直接false
4.由于括号需要相同类型闭合, 所以依次判断右括号是否栈顶依次配对, 配对出栈, 不匹配弹出返回false
5.循环结束判断栈中元素是否为0

if (str.length%2 != 0) {
        return NO;
    }
    
    NSDictionary *params = @{@"(":@")",
                             @"{":@"}",
                             @"[":@"]"
    };
    
    NSMutableArray *items = [NSMutableArray array];
    
    for (int i=0; i<str.length; i++) {
        
        NSString *c = [NSString stringWithFormat:@"%c",[str characterAtIndex:i]];
        
        if ([params.allKeys containsObject:c]) {
            [items addObject:c];
        } else {
            if (items.count !=0 && [params[items.lastObject] isEqualToString:c]) {
                [items removeLastObject];
            } else {
                return NO;
            }
        }
    }
    
    return items.count == 0;