<Hard> Remove Invalid Parentheses (LeetCode : C#)

https://leetcode.com/problems/remove-invalid-parentheses/

📕 문제 설명

괄호와 letter를 포함하는 문자열이 주어질 때 주어진 문자열이 valid하게 만들도록 invalid한 괄호를 제거한다. 이때 최소한의 제거를 할 때 가능한 문자열들을 반환 (반환할 때 순서는 상관 없음)

• Input
  괄호와 letter 포함하는 문자열 s
• Output
  최소한의 제거로 만들 수 있는 valid한 s들의 리스트

예제

풀이

DFS 사용한 풀이. 왼쪽 괄호 수와 오른쪽 괄호수가 같고 제대로 짝이 맞게 닫히는 경우가 valid한 경우다. 따라서 DFS 안에서는 다음을 진행한다.
1. left와 right 개수가 같으면 짝 판별해서 answer에 추가
2. left와 right 개수가 다르면 더 많은 것에 대해 해당되는 괄호를 제거하고 다시 DFS를 돌려 1.을 만족하는 string을 찾도록 시도

public class Solution {
    IList<string> answer;
    public IList<string> RemoveInvalidParentheses(string s) {
        answer = new List<string>();
        int left = 0; 
        int right = 0;
        
        foreach(char c in s)
        {
            if(c == '(') left ++;
            else if(c == ')')
            {
                if(left == 0) right++; 
                else left--;
            }
        }

        DFS(left, right, 0, s);
        return answer;            
    }

    private void DFS(int left, int right, int index, string s)
    {
        if(left == 0 && right == 0) // 왼쪽 오른쪽 괄호 수 같으면
        {
            if(IsValid(s)) // valid 한지 판단 
            {
                answer.Add(s);
                return;
            }
        }

        for(int i = index; i < s.Length; i++)
        {
            if(i != index && s[i] == s[i - 1]) continue;
            if(s[i] == ')' || s[i] == '(')
            {
                // 해당 괄호 뺀 string 생성
                string temp = s.Substring(0, i) + s.Substring(i + 1);

                if(left > 0 && s[i] == '(') // left 남아있으니 left 빼는 경우로 괄호 맞추기 시도
                {
                    DFS(left-1, right, i, temp); // left 뺐으니 하나 줄이고 넘김
                }
                else if(right > 0 && s[i] ==')') // right 남아있으니 right 빼는 경우로 괄호 맞추기 시도 
                {
                    DFS(left, right-1, i, temp); // right 뺐으니 하나 줄이고 넘김 
                }
            }
        } 
    }

    private bool IsValid(string s)
    {
        int count = 0;

        foreach(char c in s)
        {
            if(c =='(')
            {
                count++;
            }
            else if(c == ')')
            {
                count--;
            }
            if(count < 0) return false; // 왼쪽 보다 오른쪽이 더 많아서 invalid
        }

        return count == 0; // 제대로 다 닫혔는지 반환 
    }
}

결과