We are given a string containing just parentheses of character ')' and '(' only, find the length of the longest valid (well-formed) parentheses substring. For example, for "(()", the longest valid parentheses substring is "()", output is 2. Anther example is ")()())", the longest valid parentheses substring is "()()", which has length of 4.
Approach I: dynamic programming
As usual many of the string related problems can be solved by dynamic problem. Given a substring from index at i to j, how can we find out the longest valid parentheses substring, which is not easy to construct the dynamic function. But we can convert this problem to another problem, that is, given substring S from index i to j, find out if all of the parentheses in the substring S form valid pair.
Here is how we construct isValid dynamic function based on index i and j, which is to break the substring(i,j) to two part: i,k and k+1, j. in which k = i+1, i+3, i+5, ..., j-2.
if(isValid(i,k) && isValid(k+1,j)) then isValid(i,j) = true.
Here is the java code:
int len = str.length();
boolean[][] isValid = new boolean[len][len];
int maxLen = 0;
for(int i =0; i< len-1; i++){
if(str.charAt(i)=='(' && str.charAt(i+1) == ')'){
isValid[i][i+1] = true;
maxLen = 2;
}
}
if(isValid[i+1][j-1]&&isValid(str,i,j)) isValid[i][j] = true; for(int k=i+1; k<=j-2; k=k+2){ if(isValid[i][k] && isValid[k+1][j]) isValid[i][j] = true; if(isValid[i][j]){ maxLen = Math.max(maxLen, j - i + 1); break; } } } }
return maxLen;
}
return str.charAt(i) == '(' && str.charAt(j) == ')';
}
Approach II: using stack
Stack is great data structure, the difference between stack and queue is that you update and query from the same place: the back, while in queue you have two places to update: insert at back, remove at front. That is the reason we can use stack is constructed data structure like max/min stack and max/min queue, in this case, the queue is built on top of stack, as well.
static class Node {
int pos;
char c;
Node(int p, char c){
this.pos = p;
this.c = c;
}
}
public static int maxValidParenthesis(String input){
int max = 0;
Stack<Node> s = new Stack<Node>();
for(int i=0, j= input.length(); i<j; i++){
char c = input.charAt(i);
if(s.isEmpty() || c == '(' || s.peek().c == ')')
s.push(new Node(i, c));
else{
s.pop();
max = Math.max(i - (s.isEmpty()?-1:s.peek().pos), max);
}
}
return max;
}
For learning dp, it is a good case. But we can solve it by stack, both time and space complexity will be better.
ReplyDeleteCheck my solution, O(n) time, O(1) space. http://allenlipeng47.com/PersonalPage/index/view/188/nkey
ReplyDelete