A 13-Line C# DP Solution


  • 0
    L
    public int LongestValidParentheses(string s) {
        int[] pair = new int[s.Length];
        int result = 0;
        for(int i = s.Length - 2; i >= 0; i--){
            if(s[i] == '('){
                if(s[i + 1] == ')') pair[i] = 2;
                else if(pair[i + 1] != 0 && i + pair[i + 1] + 1 < s.Length && s[i + pair[i + 1] + 1] == ')')
                        pair[i] = pair[i + 1] + 2;
                if(pair[i] != 0 && i + pair[i] < s.Length && pair[i + pair[i]] != 0)
                    pair[i] += pair[i + pair[i]];
            }
            result = Math.Max(result, pair[i]);
        }
        return result;
    }
    

    Below is another problem and almost has nothing to do with the longest valid parenthesis.
    I pasted here for looking up.

    //remove minimum number of left and right brackets and return the string with
    //valid bracket pairs.
    //given (a))()), should return (a)(), or(a());
    //given )()()), should return either()() or(());
    //given()((9()), should return either ()(9()) or()((9)).
    private static IList<string> validParenthesis(string s){
        ISet<string> result = new HashSet<string>();
        if (s.Length == 0) return result.ToList();
        int i = 0, j = s.Length - 1;
        while (s[i] == ')') i++; while (s[j] == '(') j--;
        s = s.Substring(i, j - i + 1);
        if (s.Length == 0) return result.ToList();
        StringBuilder sb = new StringBuilder();
        for (i = 0; i < s.Length; i++) //1. find the removing subsequence
            if (s[i] == '(') sb.Append(s[i]);
            else if (s[i] == ')'){
                if (sb.Length == 0 || sb[sb.Length - 1] == ')')
                    sb.Append(s[i]);
                else sb.Length -= 1;
            }
        dfs(result, "", s, 0, sb.ToString(), 0, new Stack<char>()); //2. DFS to get all results
        return result.ToList();
    }
    
    private static void dfs(ISet<string> result, string curStr, string s, int curIndex, string toBeRemoved, int curRemove, Stack<char> valid){
        if(curRemove == toBeRemoved.Length){
            if (valid.Count == 0){
                Stack<char> stack = new Stack<char>();
                string str = s.Substring(curIndex);
                for (int i = 0; i < str.Length; i++)
                    if (str[i] != '(' && str[i] != ')') continue;
                    else if (str[i] == '(') stack.Push('(');
                    else if (stack.Count == 0) return;
                    else if (str[i] == ')') stack.Pop();
                if (stack.Count == 0) result.Add(curStr + str);
            }
            return;
        }
        if (curIndex == s.Length) return;
        if(s[curIndex] == toBeRemoved[curRemove])
            dfs(result, curStr, s, curIndex + 1, toBeRemoved, curRemove + 1, valid);
        if (s[curIndex] == '('){
            valid.Push('(');
            dfs(result, curStr + s[curIndex], s, curIndex + 1, toBeRemoved, curRemove, valid);
            valid.Pop();
        }
        else if(s[curIndex] == ')'){
            if(valid.Count == 0) return;
            else{
                valid.Pop();
                dfs(result, curStr + s[curIndex], s, curIndex + 1, toBeRemoved, curRemove, valid);
                valid.Push('(');
            }
        }
        else dfs(result, curStr + s[curIndex], s, curIndex + 1, toBeRemoved, curRemove, valid);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.