TLE on a large input but when run on my machine, gives the answer


  • 0
    P
    int longestValidParentheses(string s) {
            stack<int> parens;
            int n = s.size();
            int i = 0;
            int maxLen = INT_MIN;
            int curLen = 0;
            vector<vector<bool> > matrix(n,vector<bool>(n,false));
            while(i < n) {
                if (s[i] == '(') {
                    parens.push(i);
                } else if (!parens.empty()) {
                    int t = parens.top();
                    parens.pop();
                    matrix[t][i] = true; // s[i...j] is a valid parenthesis
                }
                i++;
            }
            //parens.clear();
            for (int l = 2;  l <= n; ++l) {
                for (int i = 0; i <= n-l; ++i) {
                    if (matrix[i][i+l-1]) {
                        maxLen = max(maxLen,l);
                        break;
                    }
                    for (int k = i+1; k < i+l-1; ++k) {
                        if (matrix[i][k] && matrix[k+1][i+l-1]) {
                            matrix[i][i+l-1] = true;
                            maxLen = max(maxLen,l);
                        }
                    }
                }
            }
            return max(maxLen, curLen);
        }

  • 0
    S

    Same here. I did a Recursion based approach.

    public class LongestValidParenthesis {
        public int longestValidParentheses(String s) {
            if(s.length() == 0 || s.length() == 1)
                return 0;
            Stack<Character> helper = new Stack<Character>();
            int max = 0;
            int index = 0;
            int orig_max = 0;
            
            return longestValidParenthesesHelper(s, helper, max, orig_max, index);
        } 
        public int longestValidParenthesesHelper(String s, Stack<Character> helper, int max, int orig_max,  int index) {
            for (int i=index; i<s.length(); i++) {
                if(s.charAt(i) == '(')
                    helper.push('(');
                else if(helper.isEmpty() && s.charAt(i) == ')') {
                	if(max > orig_max)
                		orig_max = max;
                    longestValidParenthesesHelper(s.substring(i+1), helper, 0,orig_max, i+1);
                } else if(s.charAt(i) == ')') {
                    helper.pop();
                    max += 2;
                }           
            }
            return max>orig_max?max:orig_max;
        }
    }
    

    Working on my machine, getting TLE.


Log in to reply
 

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