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

题目描述

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 - 栈

作者：人魔七七

链接：https://mp.weixin.qq.com/s/oIsmBrH5RXD0PXtqgds5ng

本公众号转载内容已尽可能注明出处，如未能核实来源或转发内容图片有权利瑕疵的，请及时联系本公众号进行修改或删除【联系方式QQ : 3442093904  邮箱：support@cocoachina.com】。文章内容为作者独立观点，不代表本公众号立场。版权归原作者所有，如申请授权请联系作者，因文章侵权本公众号不承担任何法律及连带责任。

---END---