[leetcode131] Palindrome Partitioning 문제 해결 보고서

3166 단어 leetcode

131. Palindrome Partitioning


코드 즉 문제풀이 사고방식github 주소
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Eaxmple:
Input:“aab”
Output:
[
   [“aa”,”b”],
   [“a”,”a”,”b”]
]

문제풀이의 방향


제목의 뜻은 문자열을 임의의 위치에서 여러 개의 하위 문자열로 나누는 것이다. 이 하위 문자열은 모두 회문 문자열이다.
이 문제는 모든 해를 깊이 우선 스트리밍 방법으로 스트리밍하고, 매번 구분된 하위 문자열이 회문 문자열인지 아닌지를 판단해야 한다.깊이가 우선적으로 반복되는 복잡도는 o(n^2)이고 모든 하위 문자열이 회문 문자열인지 아닌지를 동시에 판단하면 전체 알고리즘의 복잡도는 o(n^3)이다.시간의 복잡도를 낮추기 위해 n을 사용할 수 있다×n의 수조는 문자열 s[i:j]를 저장할 때 답장 문자열을 저장하고 o(1)의 시간 복잡도에서 하위 문자열이 답장 문자열인지 판단합니다.
만약 s[i:j]가 회문 문자열인지 아닌지를 판단한다면 네 가지 상황이 있다. *i==j는 회문 문자열 *s[i]=s[j]이고 i+1=j이면 회문 문자열 *s[i]=s[j]이고 s[i+1][j-1]은 회문 문자열이면 회문 문자열 *s[i]!s[j]는 메모 문자열이 아닙니다.
따라서 점차적인 공식이 있다. dp[i][j]=s[i]=s[j] and(i=jor i+1 = jor dp[i+1][j-1])
동적 기획을 통해 모든 하위 문자열이 회문 문자열인지 확인하고, 가능한 모든 구분을 깊이 있게 우선적으로 반복합니다.이때 알고리즘의 시간과 공간 복잡도는 모두 o(n^2)이다.
class Solution:
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        palindrome = [[False] * len(s) for _ in range(len(s))]

        for i in range(len(s) - 1, -1, -1):
            for j in range(i, len(s)):
                palindrome[i][j] = s[i] == s[j] and (i == j or i + 1 == j or palindrome[i + 1][j - 1])

        return self.helper(s,0,palindrome,[])

    def helper(self, s, start, palindrome, item):
        if len(s) == start:
            return [item]
        items = []
        for i in range(start, len(s)):
            if palindrome[start][i]:
                cntItem = item[:]
                cntItem.append(s[start:i+1])
                items.extend(self.helper(s,i+1,palindrome,cntItem))

        return items
React Spring을 사용한 애니메이션!
Amplify Studio 살펴보기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage