단어 나누기

문제 설명

문자열 s와 문자열 wordDict 사전이 주어지면 s를 공백으로 구분된 하나 이상의 사전 단어 시퀀스로 분할할 수 있으면 true를 반환합니다.

사전에 있는 동일한 단어가 분할에서 여러 번 재사용될 수 있습니다.

예시:
입력: s = "leetcode", wordDict = ["leet","코드"]
출력: 참
설명: "leetcode"는 "leet code"로 분할될 수 있으므로 true를 반환합니다.

예시:
입력: s = "catsandog", wordDict =["고양이","개","모래","및","고양이"]
출력: 거짓

개념

이 문제를 무차별 대입하는 것은 다소 직설적이거나 '인간적'입니다. s를 분할하려면 s를 만들기 위해 wordDict에서 단어의 결합을 만들 수 있는지 간단히 확인합니다. 간단한 접근 방식은 s의 각 세그먼트에 대해 wordDict에 일치 항목이 있는지 확인하는 것입니다. 세그먼트가 일치하는 경우 s가 끝날 때까지 일치하는 세그먼트의 연결된 경로도 있어야 합니다. 예: 세그먼트 'og'에 대한 일치 항목을 찾지 못한 경우 'cats' 및 'and'(wordDict에서)가 'catsandog'에서 일치하는 것으로는 충분하지 않습니다.

dynamic programming 솔루션은 s에서 일치하는 세그먼트를 찾을 때마다 새로운 하위 문제를 생성하므로 여기에 적용할 수 있습니다. 하위 문제는 s에서 일치하는 세그먼트를 뺀 것입니다. 우리의 기본 사례는 빈 s입니다.

나는 s의 처음부터 시작하여 재귀적인 접근을 했다. 그런 다음 함수는 s의 모든 일치에 의해 생성된 모든 하위 문제로 분리되고 하나의 하위 문제가 빈 s에 도달하면 True를 반환합니다. 즉, s의 모든 부분이 일치합니다. 이 솔루션을 시도했지만 시간 제한이 초과되었습니다. 그런 다음 계산 시간을 절약하기 위해 leetcode 토론 섹션에서 영리한 트릭을 발견했습니다.

이 솔루션의 경우 s의 모든 인덱스에 기본 사례에 대한 1을 더한 dp 배열을 만듭니다. 기본 사례를 제외하고 배열의 모든 값을 False로 설정합니다. 그런 다음 dp[i + len(matched_word)]를 확인하여 각 요소가 일치하는지 확인하고 해당 일치가 끝에 연결되어 있는지 확인하는 s의 끝에서 반복합니다. 이 방법의 장점은 결과를 캐싱하여 계산 시간을 절약한다는 것입니다.

구현

내 초기 솔루션, 재귀

class Solution:
    def wordBreak(self,s, wordDict, i=0):
        res = []
        for w in wordDict:
            if (i+len(w))<=len(s) and (s[i:i+len(w)]==w):
                if i+len(w) == len(s): return True
                else:
                    res.append(self.wordBreak(s[i+len(w):],wordDict))
        if True in res:
            return True
        return False

상향식 dp 캐싱 솔루션

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[len(s)] = True
        for i in range(len(s)-1,-1,-1):
            for w in wordDict:
                if ((i+len(w))<=len(s)) and (s[i:i+len(w)]==w):
                    dp[i] = dp[i+len(w)]
                if dp[i]:
                    break
        return dp[0]

비고

이 문제는 복잡하지 않은 것처럼 보였지만 다른 dp 문제와 다르게 만드는 흥미로운 애매함이 있었습니다. 솔루션은 단순한 시간 복잡도 이상의 계산 시간을 고려하도록 상기시킵니다. 두 솔루션 모두

O(n2*m)O(n^2*m)O(n2*m)

여기서 n은 s의 길이이고 m은 wordDict의 길이입니다. 그러나 캐싱 솔루션만 허용되었습니다. Remarkception, 여전히 dev.to의 수학적 텍스트 지원을 파악하려고 노력 중, 현재 katex를 사용 중.