leetcode hard : Remove Invalid Parenthesis

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

Remove Invalid Parentheses - LeetCode

 

하 ... 1 <= s.length <= 25 .. ㅋㅋㅋㅋㅋㅋㅋ

또 너냐 백트래킹;;

 

일단 각 괄호를 지울까 말까 선택하는 전체탐색트리를 생각해보면 2^25가 최대 경우의 수고 약 3천만. 백트래킹으로 해결해볼만 하다.

어 근데 BFS가 왜있지? 아 minimum number of removals!

사실 전체탐색트리의 노드 개수가 3천만이고 validness 검사하고 이런거까지 생각하면 pruning할 방법이 필요하긴 했는데

bfs를 써서 같은레벨의 노드들은 removal count가 같도록 하면 될거같다.

그리고 ( 개수랑 ) 개수를 세서 더 많은쪽을 remove해야된다. 이런 여러가지것들을 고려하면 탐색트리의 크기를 꽤 줄일 수 있을것같다.

 

Time Limit Exceeded (86 / 127 tc passed)

아 .. 왜 ..

Last Executed Input s = "))(((((()())(()"

 

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        def isValid(pstr):
            c = 0
            for ch in pstr:
                if ch == ')':
                    if c == 0:
                        return False
                    c -= 1
                elif ch == '(':
                    c += 1
            return c == 0

        q = deque([(s, s.count('('), s.count(')'))])
        answer_set = set()

        while q:
            print("qlength", len(q))
            for i in range(len(q)):
                s, op, cl = q.popleft()

                if op > cl:
                    for j in range(len(s)):
                        if s[j] == '(':
                            q.append((s[:j]+s[j+1:], op-1, cl))
                elif op < cl:
                    for j in range(len(s)):
                        if s[j] == ')':
                            q.append((s[:j]+s[j+1:], op, cl - 1))
                else:
                    if isValid(s):
                        answer_set.add(s)
                    else:
                        for j in range(len(s)):
                            if s[j] == '(':
                                q.append((s[:j]+s[j+1:], op-1, cl))
                            if s[j] == ')':
                                q.append((s[:j]+s[j+1:], op, cl - 1))
            if answer_set:
                break
        
        return list(answer_set)

아마 (랑 )의 개수가 같아지는 시점부터 속도가 매우 느려질거같다.

근데 사실 '))((' 이렇게 쌍이 첨부터 어긋나고 시작하는 경우는 굳이 하나하나 제거해볼 필요는 없는데

이런 경우 고려해서 pruning이 더 필요한걸까?

 

근데 생각해보면 재밌는 사실을 알수있다.

s를 스캔해보면 우린 final expression에 (랑 )가 몇개 들어가야될지 알 수 있다.

힌트는 valid check하는 함수에서 얻을 수 있는데

def isValid(pstr):
    c = 0
    for ch in pstr:
        if ch == ')':
            if c == 0:
                return False
            c -= 1
        elif ch == '(':
            c += 1
    return c == 0

)가 나왔을때 c가 0이면 해당 )는 invalid한 closing parenthesis다.

그리고 for loop이 끝나고 나서 c가 0보다 크면 그건 invalid한 opening parenthesis다.

그럼 ))(()()(()))((() 에서

) ) ( ( ) ( ) ( ( ) ) ) ( ( ( )

밑줄 친 부분이 invalid closing parenthesis로 개수가 잡혀 2개가 나오고

오른쪽 끝 4개의 글자에서 c가 2가 남아버려서 invalid opening parenthesis 개수가 2개가 잡힌다.

그럼 우린 둘을 합쳐 invalid parenthesis의 개수를 미리 알 수 있고 이걸 M이라고 하면

2^M으로 프루닝을 좀 할 수 있다. 

근데 M <= N이라 ))))((((같은 경우는 최악이다.

그럼 오픈된 parenthesis가 없는데 지혼자 툭 튀어나오는 )는 미리 짤라놓고 시작할 수 있지 않을까?

라고 생각했는데 이건 보기좋은 반례가 있다.

Input: s = "()())()"
Output: ["(())()","()()()"]

내가 생각한대로 )를 미리 다 짤라놓고 시작하면 여기서 ()()()밖에 안나옴.

 

흠..

그럼 맨 첨에 나오는 )만 없애놓을까?

 

그냥 솔루션을 봐야겠다.

public List<String> removeInvalidParentheses(String s) {
    List<String> ans = new ArrayList<>();
    remove(s, ans, 0, 0, new char[]{'(', ')'});
    return ans;
}

public void remove(String s, List<String> ans, int last_i, int last_j,  char[] par) {
    for (int stack = 0, i = last_i; i < s.length(); ++i) {
        if (s.charAt(i) == par[0]) stack++;
        if (s.charAt(i) == par[1]) stack--;
        if (stack >= 0) continue;
        for (int j = last_j; j <= i; ++j)
            if (s.charAt(j) == par[1] && (j == last_j || s.charAt(j - 1) != par[1]))
                remove(s.substring(0, j) + s.substring(j + 1, s.length()), ans, i, j, par);
        return;
    }
    String reversed = new StringBuilder(s).reverse().toString();
    if (par[0] == '(') // finished left to right
        remove(reversed, ans, 0, 0, new char[]{')', '('});
    else // finished right to left
        ans.add(reversed);
}

)만 지우는 함수를 만들고 s를 뒤집어서 반대의 경우를 같은 함수로 돌리면 된다는데..

흠.. 너무 어렵다

 

class Solution:  # 40 ms, faster than 93.29%
    def removeInvalidParentheses(self, s: str) -> List[str]:
        @lru_cache(None)
        def dfs(i, nOpen):
            ans = set()
            if nOpen < 0:
                return ans  # Invalid -> return 0 result
            if i == len(s):
                if nOpen == 0: ans.add("")  # Valid -> Return 1 result (empty string)
                return ans

            if s[i] == '(' or s[i] == ')':  # Case 1: Skip s[i]: '(', ')'
                ans.update(dfs(i + 1, nOpen))

            if s[i] == '(':
                nOpen += 1
            elif s[i] == ')':
                nOpen -= 1
            for suffix in dfs(i + 1, nOpen):  # Case 2: Include s[i]: '(', ')' or letter
                ans.add(s[i] + suffix)
            return ans

        validParentheses = dfs(0, 0)
        maxLen = max(map(len, validParentheses))
        return filter(lambda x: len(x) == maxLen, validParentheses)

이해하는데 좀 걸렸는데 꽤 창의적인 코드다.

dfs(i, nOpen)은 s[i:]에서 invalid parenthesis를 제거한 set을 리턴한다.

 

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        def helper(open_brace, close_brace, results, reverse):            
            count = {open_brace: 0, close_brace: 0}
            removed = 0
            for i in range(len(s)):
                c = s[-(i+1)] if reverse else s[i]
                if c == close_brace and count[open_brace] == count[close_brace]:
                    new_results = set()
                    for result in results:
                        if reverse:
                            r = range(len(result) - (i - removed + 1), len(result))
                        else:
                            r = range(i - removed + 1)
                
                        for j in r:
                            if result[j] == close_brace:
                                new_results.add(result[:j] + result[j + 1:])
                    results = new_results
                    removed += 1
                elif c in count:
                        count[c] += 1
            return results

        results = {s}
        results = helper("(", ")", results, False)
        results = helper(")", "(", results, True)
        return list(results)

이해가 안된다

 

public class Solution {
    public List<String> removeInvalidParentheses(String s) {
      List<String> res = new ArrayList<>();
      
      // sanity check
      if (s == null) return res;
      
      Set<String> visited = new HashSet<>();
      Queue<String> queue = new LinkedList<>();
      
      // initialize
      queue.add(s);
      visited.add(s);
      
      boolean found = false;
      
      while (!queue.isEmpty()) {
        s = queue.poll();
        
        if (isValid(s)) {
          // found an answer, add to the result
          res.add(s);
          found = true;
        }
      
        if (found) continue;
      
        // generate all possible states
        for (int i = 0; i < s.length(); i++) {
          // we only try to remove left or right paren
          if (s.charAt(i) != '(' && s.charAt(i) != ')') continue;
        
          String t = s.substring(0, i) + s.substring(i + 1);
        
          if (!visited.contains(t)) {
            // for each state, if it's not visited, add it to the queue
            queue.add(t);
            visited.add(t);
          }
        }
      }
      
      return res;
    }
    
    // helper function checks if string s contains valid parantheses
    boolean isValid(String s) {
      int count = 0;
    
      for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') count++;
        if (c == ')' && count-- == 0) return false;
      }
    
      return count == 0;
    }
}

이게 진짜 clean and concise solution이지! (내가 처음에 한 발상이랑 같은 방향의 솔루션이라 더 편하게 느낄지도..)

내가 첨에 했던거랑 다른점은.. 나는 visited 체크랑 valid한걸 발견했을때 continue를 안했던거같다. 내 코드를 수정해보자.

 

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        def isValid(pstr):
            c = 0
            for ch in pstr:
                if ch == ')':
                    if c == 0:
                        return False
                    c -= 1
                elif ch == '(':
                    c += 1
            return c == 0

        visited = set()
        visited.add(s)

        q = deque([s])
        answer_set = set()

        answerFound = False
        while not answerFound:
            for i in range(len(q)):
                s = q.popleft()

                if isValid(s):
                    answer_set.add(s)
                    answerFound = True
                    continue

                if answerFound:
                    continue

                for j in range(len(s)):
                    if s[j] in '()':
                        nxt = s[:j]+s[j+1:]
                        if nxt not in visited:
                            q.append(nxt)
                            visited.add(nxt)

        
        return list(answer_set)

됐다! Accepted