"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

动态规划：

 1     public int maxLength(String str)
 2     {
 3         if(str == null || str.equals(""))
 4         {
 5             return 0;
 6         }
 7 
 8         char[] chas = str.toCharArray();
 9         int[] dp = new int[chas.length];
10         int pre = 0;
11         int res = 0;
12         for(int i = 1; i < chas.length; i++)
13         {
14             if(chas[i] == ')')
15             {
16                 pre = i - dp[i - 1] - 1;
17                 if(pre >= 0 && chas[pre] == '(')
18                 {
19                     dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
20                 }
21             }
22             res = Math.max(res, dp[i]);
23         }
24         return res;
25     }

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