题目描述

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

思路描述

代码实现

- (BOOL)isValid:(NSString *)inputStr
{
//1
    if (inputStr.length == 0 || inputStr.length%2 == 1)
    {
        return NO;
    }
//2
    DSStack *newStack = [[DSStack alloc] initWithSize:10];

    for (int i =0 ; i<inputStr.length; i++)
    {
    //3 
        unichar tempChar = [inputStr characterAtIndex:i];
        if (tempChar =='(' || tempChar =='{' || tempChar == '[')
        {
            [newStack push:[NSString stringWithCharacters:&tempChar length:1]];
        }
        //4
        else
        {
            if (newStack && [self isPairLeftAndRight:[newStack peek] right:[NSString stringWithCharacters:&tempChar length:1]])
            {
                [newStack popLastObject];
            }
            else
            {
                return NO;
            }
        }
    }

    //5
    return [newStack isEmpty];

}

代码思路描述：

1. 如果输入字符串是空或者奇数则invalid。

2. 创建一个新的stack。

3. 遍历字符串把含有（ { [ 字符放到栈里便于匹配。

4. 如果栈顶字符和tempChar字符匹配则栈顶字符出栈，否则invalid。

5. 匹配完毕如果stack是空则valid。

复杂度估算

• Time Complexity: O(n)

• Space Complexity: O(n) ，由于借助stack存储

Demo

https://github.com/renmoqiqi/100-Days-Of-iOS-DataStructure-Algorithm/tree/master/Day03

• 100天iOS数据结构与算法实战 Day01

• 100天iOS数据结构与算法实战 Day02 - 栈