1249. Minimum Remove to Make Valid Parentheses / TypeScript

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

• It is the empty string, contains only lowercase characters, or
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

 

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

 

출처 : https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/

 

 

풀이

function minRemoveToMakeValid(s: string): string {
    let stack = 0

    for (let i = 0; i < s.length; i++) {
        const char = s[i]
        if (char === '(') { stack++; continue }

        if (char === ')') {
            if (stack) {
                stack--
                continue
            }
            s = s.slice(0, i) + s.slice(i + 1)
            i--
        }
    }

    for(let i = s.length - 1; stack !== 0; i--) {
        const char = s[i]
        if (char === '(') {
            s = s.slice(0, i) + s.slice(i + 1)
            i++
            stack--
        }
    }

    return s
};

 

 

 

• 스택 초기화: stack 변수를 0으로 초기화합니다. 이 변수는 여는 괄호 (의 개수를 추적
• 첫 번째 루프: 문자열 s를 처음부터 끝까지 순회
  • 현재 문자 char가 여는 괄호 (이면 stack을 증가시키고 다음 문자로 넘어감.
  • 현재 문자가 닫는 괄호 )이면:
    • stack이 0보다 크면(여는 괄호가 존재하면) stack을 감소시키고 다음 문자로 넘어감.
    • 그렇지 않으면(여는 괄호가 없으면) 현재 닫는 괄호를 제거.
    • 이때, 문자열 s에서 현재 위치 i의 문자를 제거하고 i를 하나 줄여서 다음 반복에서 다시 현재 위치를 검사하게 함.
• 두 번째 루프: 문자열 s를 뒤에서부터 앞으로 순회하면서 스택이 0이 될 때까지 반복합니다.
  • 현재 문자 char가 여는 괄호 (이면:
    • 여는 괄호를 제거하고 stack을 감소.
    • 제거 후, i를 하나 증가시켜 다음 반복에서 올바른 위치를 검사.
• 결과 반환: 모든 불필요한 괄호가 제거된 문자열 s를 반환

 

s = s.slice(0, i) + s.slice(i + 1)

1. s.slice(0, i): 문자열 s의 처음부터 i번째 문자 직전까지의 부분 문자열을 반환.
   1. 즉, s의 0부터 i-1까지의 문자를 포함.
2. s.slice(i + 1): 문자열 s의 i+1번째 문자부터 끝까지의 부분 문자열을 반환.
   1. 즉, s의 i+1부터 마지막 문자까지를 포함.
3. + 연산: 두 부분 문자열을 연결
   1. . 이는 i번째 문자를 제외한 문자열을 생성.

즉, s = s.slice(0, i) + s.slice(i + 1)는 문자열 s에서 i번째 문자를 제거한 새로운 문자열을 생성하는 코드

 

 

 

문자열 s가 "a)b(c)d)"인 경우

1. 초기화

• stack을 0으로 초기화.

2. 첫 번째 루프

문자열을 처음부터 끝까지 순회.

• i=0: char는 'a'.
  • 괄호가 아니므로 그대로 넘어감.
• i=1: char는 ')'. stack이 0이므로, 여는 괄호가 없는 상태에서 닫는 괄호가 나옴. 이 닫는 괄호를 제거.
  • 문자열 s는 "ab(c)d)"로 변경되고, i는 0 (현재 위치를 다시 검사).
• i=1: char는 'b'.
  • 괄호가 아니므로 그대로 넘어갑니다.
• i=2: char는 '('.
  • stack을 1로 증가.
• i=3: char는 'c'.
  • 괄호가 아니므로 그대로 넘어감.
• i=4: char는 ')'.
  • stack이 1이므로, 유효한 닫는 괄호. stack을 0으로 감소.
• i=5: char는 'd'.
  • 괄호가 아니므로 그대로 넘어감.
• i=6: char는 ')'.
  • stack이 0이므로, 여는 괄호가 없는 상태에서 닫는 괄호가 나옴. 이 닫는 괄호를 제거.
  • 문자열 s는 "ab(c)d"로 변경되고, i는 5(현재 위치를 다시 검사).

이 단계가 끝나면 문자열은 "ab(c)d"이고, stack은 0입니다.

3. 두 번째 루프

문자열을 뒤에서부터 앞으로 순회합니다.

• stack이 0이므로, 두 번째 루프는 실행되지 않습니다.

4. 결과 반환

최종 문자열 "ab(c)d"를 반환

 

 

두 번째 루프가 도는 예시 

s = "))(("

 

첫번째 루프에서 (( 만 남고, stack 은 2 인상태여서 두번째 루프가 돌면서 )) 제거