100天iOS数据结构与算法实战 Day03 - 栈的算法实战 Valid Parentheses

人魔七七 2019-03-28 10:04:21 635

题目描述

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.

思路描述

640 (2).gif

代码实现

  1. - (BOOL)isValid:(NSString *)inputStr

  2. {

  3. //1

  4.    if (inputStr.length == 0 || inputStr.length%2 == 1)

  5.    {

  6.        return NO;

  7.    }

  8. //2

  9.    DSStack *newStack = [[DSStack alloc] initWithSize:10];


  10.    for (int i =0 ; i<inputStr.length; i++)

  11.    {

  12.    //3

  13.        unichar tempChar = [inputStr characterAtIndex:i];

  14.        if (tempChar =='(' || tempChar =='{' || tempChar == '[')

  15.        {

  16.            [newStack push:[NSString stringWithCharacters:&tempChar length:1]];

  17.        }

  18.        //4

  19.        else

  20.        {

  21.            if (newStack && [self isPairLeftAndRight:[newStack peek] right:[NSString stringWithCharacters:&tempChar length:1]])

  22.            {

  23.                [newStack popLastObject];

  24.            }

  25.            else

  26.            {

  27.                return NO;

  28.            }

  29.        }

  30.    }


  31.    //5

  32.    return [newStack isEmpty];


  33. }

代码思路描述:

  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