"Coding Interview Guide" -- 括号字符串的有效性和最长有效长度

题目

  给定一个字符串str,判断是不是整体有效的括号字符串

  举例,str = "()",返回true;str = "(()())",返回true;str = "(())",返回true;

       str = "())",返回false;str = "()(",返回false;str = "()a()",返回false;

my:

 1     import java.util.Stack;
 2 
 3     public boolean my_isValid(String str)
 4     {
 5         if(str == null || str.equals(""))
 6         {
 7             return false;
 8         }
 9 
10         char[] cstr = str.toCharArray();
11         Stack<Character> stack = new Stack<>();
12         for(char c : cstr)
13         {
14             if(c == '(')
15             {    
16                 stack.push(c);
17             }
18             else if(c == ')')
19             {
20                 if(stack.empty())
21                 {
22                     return false;
23                 }
24                 stack.pop();
25             }
26             else
27             {
28                 return false;
29             }
30         }
31         return stack.empty() ? true : false;
32     }

时间复杂度:O(N),空间复杂度:O(N)

 

左老师:

 1     public boolean isValid(String str)
 2     {
 3         if(str == null || str.equals(""))
 4         {
 5             return false;
 6         }
 7 
 8         char[] chas = str.toCharArray();
 9         int count = 0;     // 简单地设置一个计数器
10         for(char c : chas)
11         {
12             if(c != '(' && c != ')')
13             {
14                 return false;
15             }
16             if(c == ')' && --count < 0)
17             {
18                 return false;
19             }
20             if(c == '(')
21             {
22                 count++;
23             }
24         }
25 
26         return count == 0;
27     }

时间复杂度:O(N),空间复杂度:O(1)

 

【进阶题目】

  给定一个括号字符串str,返回最长的有效括号子串

  举例,str = "(()())",返回6;str = "())",返回2;str = "()(()()(",返回4

 

 

 

来源:左程云老师《程序员代码面试指南》

上一篇:matplotlib 进阶之Legend guide


下一篇:【BZOJ5197】Gambling Guide (最短路,期望)