856. Score of Parentheses
June 24, 2025
04:32 AM
No headings found
Loading content...
No headings found
Problem
Approach - Depth counting
Ý tưởng chính của cách này là theo dõi độ sâu của các cặp ngoặc lồng nhau. Mỗi khi gặp một cặp ngoặc đơn “()”, ta cộng vào kết quả giá trị 2^depth, trong đó depth là độ sâu của dấu ngoặc ngay trước khi đóng lại.
1Chuỗi: ( ( ) ( ( ) ) )
2Depth: 1 2 1 2 3 2 1 0
3Điểm cộng: +2 +4
4Tổng điểm: 2 + 4 = 6Time and space complexity:
Solution
1function scoreOfParentheses(s: string): number {
2 let score = 0;
3 let depth = 0;
4
5 for(let i = 0; i < s.length; i++) {
6 if(s[i] === "(") {
7 depth++;
8 } else {
9 depth--;
10 if(s[i - 1] === "(") {
11 score += 1 << depth;
12 }
13 }
14 }
15
16 return score;
17}