Remove Invalid Parentheses | LeetCode 301 | Python3 🐍

 

📄 목차

 

 

제목:  https://leetcode.com/problems/remove-invalid-parentheses/🐍

🤔 문제 : Remove Invalid Parentheses | LeetCode 301

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

주어진 문자열에서 가장 긴 palindrome을 찾는 문제입니다.

 

 

💡 풀이

1. 구구절절.. iteration

주어진 s의 모든 substring에 대해서, valid parenthesis 여부를 확인하면서, 가장 긴 것들을 저장해서 반환해야 겠다.

그럼 TLE 가 날 것 같으니, (와 )의 갯수를 대조해서 더 많은걸 많은 갯수만큼 삭제한 substring먼저 확인하고.. 거기서 없으면 (와 )를 하나씩 더 삭제하고..

 

등등의 로직을 담은 코드를 작성하였고 어찌어찌 통과는 되었네요.

하지만 다시는 읽고싶지 않은 길이의 코드가 되었으니.. 뭔가 단단히 잘못된 것 같죠..

from typing import List

# s = "()())()"
# => ["(())()","()()()"]
class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        # 제거하는 모든 조합을 만들어서 valid 체크

        # valid 여부 확인, 문자열에서 포함 안할 idx 지정 - O(N)
        def isParenthesisSkip(s: str, skipOrg: List[int]) -> bool:
            skip = skipOrg[:]

            # 건너뛸게 문자면 pass
            chars_to_skip = [ (s[idx] == '(' or s[idx] == ')') for idx in skip]
            if not all(chars_to_skip):
                return False

            # 건너뛸게 문자는 포함하지 않고 parenthesis check
            stack = []
            toskip = skip.pop(0) if len(skip) > 0 else -1

            for idx, c in enumerate(s):
                if idx == toskip:
                    toskip = skip.pop(0) if len(skip) > 0 else -1
                    continue

                # print('stack: ', stack, 'skip idx: ', toskip)
                if c == '(':
                    stack.append(c)
                elif c == ')':
                    if len(stack) == 0 or stack[-1] != '(':
                        return False
                    stack.pop()
            if len(stack) == 0:
                return True
            return False
        
        def trim(s: str) -> str:
            # 문자열 앞부분의 ), 뒷부분의 ( 삭제
            idx_front = -1
            idx_back = -1
            for idx, c in enumerate(s):
                if c != ')':
                    idx_front = idx
                    break
            
            for idx, c in enumerate(reversed(s)):
                if c != '(':
                    idx_back = idx
                    break
            return s[idx_front: len(s)-idx_back]

        def powerset(s):
            x = len(s)
            masks = [1 << i for i in range(x)]
            for i in range(1 << x):
                yield [ss for mask, ss in zip(masks, s) if i & mask]

        def make_string(s, idx_to_remove_org):
            # array deep copy
            idx_to_remove = idx_to_remove_org[:]

            if len(idx_to_remove) == 0:
                return s
            
            ret = ""
            idx_to_remove_next = idx_to_remove.pop(0)
            for idx, char in enumerate(s):
                if idx == idx_to_remove_next:
                    idx_to_remove_next = idx_to_remove.pop(0) if len(idx_to_remove) > 0 else -1
                else:
                    ret += char
            return ret

        trimed_string = trim(s)

        # ( 와 )의 위치들을 저장
        position_op = []
        position_cp = []
        for idx, c in enumerate(trimed_string):
            if c =='(':
                position_op.append(idx)
            elif c == ')':
                position_cp.append(idx)
        
        # ( 와 )의 갯수를 비교하여 차이를 계산
        diff = len(position_op) - len(position_cp)
        skip_num_op = max(diff, 0)
        skip_num_cp = max(-diff, 0)
        
        # possible skip options
        postion_list_op = list(powerset(position_op))
        postion_list_cp = list(powerset(position_cp))

        result_found = False
        result = []
        while skip_num_op <= len(position_op) and skip_num_cp <= len(position_cp) and not result_found:
            op_skip_list = list(filter(lambda x: len(x) == skip_num_op, postion_list_op))
            cp_skip_list = list(filter(lambda x: len(x) == skip_num_cp, postion_list_cp))

            if len(op_skip_list) == 0:
                for cp_skip in cp_skip_list:
                    skip_options =sorted(cp_skip)

                    if isParenthesisSkip(trimed_string, skip_options):
                        result_found = True
                        result.append(make_string(trimed_string, skip_options))
            elif len(cp_skip_list) == 0:
                for op_skip in op_skip_list:
                    skip_options =sorted(op_skip)

                    if isParenthesisSkip(trimed_string, skip_options):
                        result_found = True
                        result.append(make_string(trimed_string, skip_options))

            else:
                for op_skip in op_skip_list:
                    for cp_skip in cp_skip_list:
                        skip_options =sorted(op_skip+cp_skip)

                        if isParenthesisSkip(trimed_string, skip_options):
                            result_found = True
                            result.append(make_string(trimed_string, skip_options))

            skip_num_op += 1
            skip_num_cp += 1

        return list(set(result))

 

2. DFS

어쩐지 코드가 구구절절하다 싶으면..  DFS나 BFS로 풀어야 할 걸 iteration으로 풀어야 한 경우가 많았습니다. 

이번에도 역시나 discussion을 확인해보니 DFS풀이가 많았습니다.

DFS로 다시 코드를 작성해보았습니다.

from typing import List

# s = "()())()"
# => ["(())()","()()()"]
class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        self.longest_str_size = -1
        self.result = []

        self.isValidParenthesis(s, len(s), '', 0, 0, 0)
        return list(set(self.result)) 

    def isValidParenthesis(self, s: str, lens: int, currs: str, idx: int, num_o, num_c):
            if num_c > num_o:
                return False

            # 마지막까지 다 봤음
            if lens == idx:
                # print('isValidParenthesis', idx, currs, num_c, num_o, self.longest_str_size)

                if num_c != num_o:
                    return False
                else:
                    if len(currs) > self.longest_str_size:
                        self.longest_str_size = len(currs)
                        self.result = [currs]
                        return True
                    elif len(currs) == self.longest_str_size:
                        self.result.append(currs)
                        return True
                    else:
                        return False

            self.isValidParenthesis(s, lens, currs+s[idx], idx+1, num_o + (1 if s[idx] == "(" else 0), num_c+ (1 if s[idx] == ")" else 0))
            self.isValidParenthesis(s, lens, currs, idx+1, num_o, num_c)

 

한결 깔끔해졌지만 결과는 TLE. 

문자열의 길이가 N이라고 할때 DFS는 O(2^N) 이죠.

 

 

3.  DFS + pruning

DFS에서 불가능한 가지들을 사전에 pruning하는 방식으로 최종 답을 제출하였습니다.

 

아래 코드의 [2], [4]에 대한 부연설명입니다.

 

[2] skip갯수 기반 pruning

valid parentheses 중 가장 긴 것을 찾는 문제입니다. 

만약 이미 찾은 valid parentheses가 삭제한 문자는 1개인데 지금 확인하는 문자열은 이미 2개를 삭제했다면, 이 문자열이 valid한들 가장 긴 valid parentheses는 될 수 없으므로 정답이 아닙니다. 

 

[3] valid parentheses가 될 가능성이 있는지 확인

valid parentheses는 ( 와 )의 갯수가 같다는 특징이 있습니다.

만약 현재 문자열에 (가 10개인데 남은 ) 를 다 쓴다고 해도 5개밖에 안된다면 이 문자열은 valid parentheses가 될 가능성이 없습니다. 

 

')'의 갯수가 '('보다 많은 시점이 한번이라도 있다면 이미 [1]에서 invad parentheses로 False를 리턴할 것이기 때문에 해당 케이스는 고려하지 않습니다.

 

는 (와 )의 갯수가 같다는 특징이 있습니다. 

from typing import List

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        self.longest_str_size = -1
        self.result = []

        self.dfs(s, len(s), '', 0, 0, 0, 0, s.count('('), s.count(')'))
        return list(set(self.result))

    def dfs(self, s: str, lens: int, currs: str, idx: int, num_o, num_c, num_skip, remaining_o, remaining_c):
            # [1] valid parenthesis인지 확인
            if num_c > num_o:
                return False
            
            # [2] skip갯수 기반 pruning
            if num_skip > lens-self.longest_str_size:
                return False
            
            # [3] valid parentheses가 될 가능성이 있는지 확인
            if num_o > num_c + remaining_c:
                return False

            # 마지막 인덱스인 경우 validity check
            if lens == idx:
                # print('isValidParenthesis', idx, currs, num_c, num_o, self.longest_str_size)

                if num_c != num_o:
                    return False
                else:
                    if len(currs) > self.longest_str_size:
                        self.longest_str_size = len(currs)
                        self.result = [currs]
                        return True
                    elif len(currs) == self.longest_str_size:
                        self.result.append(currs)
                        return True
                    else:
                        return False

            self.dfs(s, lens, currs+s[idx], idx+1, num_o + (1 if s[idx] == "(" else 0), num_c+ (1 if s[idx] == ")" else 0), num_skip, remaining_o-(1 if s[idx] == "(" else 0), remaining_c-(1 if s[idx] == ")" else 0))
            self.dfs(s, lens, currs, idx+1, num_o, num_c, num_skip+1, remaining_o-(1 if s[idx] == "(" else 0), remaining_c-(1 if s[idx] == ")" else 0))