leetcode-ts/leetcode/0032.longest-valid-parentheses/index.ts at master · guocaoyi/leetcode-ts · GitHub

Name: leetcode-ts/leetcode/0032.longest-valid-parentheses/index.ts at master · guocaoyi/leetcode-ts · GitHub
Rating: 4.9 (837 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/**
 * # 32. Longest Valid Parentheses
 *
 * Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.
 *
 * ## Example
 *
 * ```bash
 * Input: "(()"
 * Output: 2
 * Explanation: The longest valid parentheses substring is "()"
 * ```
 * ```bash
 * Input: ")()())"
 * Output: 4
 * Explanation: The longest valid parentheses substring is "()()"
 * ```
 *
 * ## Thinking
 *
 * - 消消乐
 */
exporttypeSolution=(s: string)=>number;

/**
 * @date 2020/07/04 11:58:00
 * @time O(kn)
 * @space O(n)
 * @runtime
 * @memory
 * @runtime_cn 104 ms, faster than 23.8%
 * @memory_cn 40.1 MB, faster than 100.00%
 */
exportconstlongestValidParentheses=(s: string): number=>{
constlen: number=s.length;
conststack: {index: number;char: string}[]=[];
consttip=newArray(len);
for(leti=0;i<len;i++){
stack.push({index: i,char: s.charAt(i)});
constlen=stack.length;
if(len>=2){
constsum=stack[len-2].char+stack[len-1].char;
if((sum==="()"||sum==="{}"||sum==="[]")){
constpre=stack.pop();
constnext=stack.pop();
tip[pre?.indexasnumber]=1;
tip[next?.indexasnumber]=1;
}
}
}
letmaxLen=0;
letLen=0;
for(leti=0;i<tip.length;i++){
if(tip[i]===1){
Len+=1;
maxLen=Math.max(maxLen,Len);
}else{
Len=0;
}
}
returnmaxLen;
};

/**
 * @time
 * @space
 */
exportconstlongestValidParentheses1=(s: string): number=>{
constlen: number=s.length;
conststack: {index: number;char: string}[]=[];
consttip=newArray(len);
for(leti=0;i<len;i++){
stack.push({index: i,char: s.charAt(i)});
constlen=stack.length;
if(len>=2){
constsum=stack[len-2].char+stack[len-1].char;
if((sum==="()"||sum==="{}"||sum==="[]")){
constpre=stack.pop();
constnext=stack.pop();
tip[pre?.indexasnumber]=1;
tip[next?.indexasnumber]=1;
}
}
}
letmaxLen=0;
letLen=0;
for(leti=0;i<tip.length;i++){
if(tip[i]===1){
Len+=1;
maxLen=Math.max(maxLen,Len);
}else{
Len=0;
}
}
returnmaxLen;
};