856. Score of Parentheses
Tags:
Medium
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
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}