[코테] 리트코드 파이썬 131번 Palindrome Partitioning 회문

Palindrome Partitioning - LeetCode

 

문자열의 partition의 모든 substring이 회문이라면 결과리스트로 리턴하는 문제이다.

첫 시도는 for 반복문을 세번째 인자를 사용하여 문자열의 길이만큼 뛰어넘으며 partition을 확인했다. 해당 partition의 모든 substring이 회문인지 check(s) 함수를 통해 확인했다. 이와 같은 코드는 테스트코드는 통과했지만 최종 제출에서는 통과하지 못했다. 그 이유는 for를 사용하여 뛰어넘으며 partition을 나누면 확인하지 못한 partition이 있기 때문이다.

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        array=[]
        def check(s):
            one=len(s)
            if one%2==0:
                if s[:one//2]==s[one//2:][::-1]:
                    return True
                else:
                    return False
            else:
                if s[:one//2]==s[one//2+1:][::-1]:
                    return True
                else:
                    return False

        
        for i in range(len(s)):
            result=[]
            cnt=0
            for j in range(0,len(s),i+1):
                result.append(s[j:i+1+j])
            for j in result:
                if check(j):
                    cnt+=1
            print(result)
            if cnt==len(result):
                array.append(result)


        return array

최종 정답은 파티션으로 나눈 후, self.partition()을 재귀적으로 호출하여 남은 문자열을 partition으로 나누는 방법을 사용한다. 재귀적으로 나눈 것과 현재 나눠진 것을 합치면 최종적으로 문자열의 partition이 된다.

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        ans = []
        if n == 0:
            return [[]]
        for i in range(1, n + 1):
            if s[:i] != s[:i][::-1]:
                continue

            cur = self.partition(s[i:])
            for j in range(len(cur)):
                ans.append([s[:i]] + cur[j])
        return ans