[LeetCode] 678. Valid Parenthesis String

😎풀이

1. *로 잘못된 괄호를 제거할 수 있음
   1-1. 단, (의 이후에 선언되었거나, ) 이전에 선언된 *만 가능하므로 스택에 인덱스 형태로 저장
2. s 순회
   2-1. 닫는 괄호는 열린 괄호로 제거하거나, *로 처리
3. 남은 열린 괄호는 *로 처리 가능한 만큼 처리
4. 모든 괄호가 정상적으로 처리되었는지 여부 반환

function checkValidString(s: string): boolean {
    const pStack = []
    const aStack = []
    for(let i = 0; i < s.length; i++) {
        const char = s[i]
        if(char === '(') {
            pStack.push(i)
        } else if(char === '*') {
            aStack.push(i)
        } else if(char ===')') {
            if(pStack.length === 0 && aStack.length === 0) return false
            if(pStack.length > 0) pStack.pop()
            else aStack.pop()
        }
    }
    while(pStack.length && aStack.length) {
        const lastAsterisk = aStack.pop()
        if(pStack.at(-1) > lastAsterisk) return false
        pStack.pop()
    }
    return pStack.length === 0
};