leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

longest-valid-parentheses.js (1481B)

      1 //This is the brute force to a problem which is to find the longest set of valid parenthesis in a 
      2 //list of parenthesis. The time complexity of this code is O(n^2) where n is the length of the string.
      3 //This is because for every value you have to iterate through all others values in the worst case.
      4 //Time: 3027ms Beats: 5.3%
      5 //Memory: 82.5MB Beats: 5.3%
      6 
      7 /**
      8  * @param {string} s
      9  * @return {number}
     10  */
     11 var longestValidParentheses = function(s) {
     12     let longest = 0;
     13     for(let i = 0 ; i < s.length ; ++i){
     14         let current_string = s.substring(i);
     15         let check_val = check_valid(current_string);
     16         if(check_val > longest){
     17             longest = check_val; 
     18         }
     19     }
     20     return longest;
     21 };
     22 
     23 function check_valid(s){
     24     let max = 0;
     25     let curr_max = 0;
     26     let vals = [];
     27     for(let i = 0 ; i < s.length ; ++i){
     28         let curr = s[i];
     29         if(curr == '[' || curr == '{' || curr == "("){
     30             vals.push(curr);
     31         }
     32         else{
     33             if (vals.length == 0) {
     34                 return max;
     35             }
     36             let popped = vals.pop();
     37             if(
     38                 popped == '[' && curr != ']' ||
     39                 popped == '(' && curr != ')' ||
     40                 popped == '{' && curr != '}'
     41                 ){
     42                     return max;
     43                 }
     44             else{
     45                 curr_max += 2;
     46             }
     47         }
     48         if(vals.length == 0){
     49             max = curr_max;
     50         }
     51     }
     52     return max;
     53 }