[LeetCode] 139. Word Break

접근

• 완전탐색이 아닌 DP로 풀어야 하는 문제
• DP[0]에 도달하여 True를 리턴하면 되기에 Bottom-up 방식으로 문제를 풀 수 있다.
• DP 리스트 길이를 s의 길이보다 하나 더 길게 설계하여 부드러운 솔루션을 작성해야 함

 

문제 링크

https://leetcode.com/problems/word-break/description/

 

솔루션

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        s_length = len(s)
        DP = [False for _ in range(s_length+1)]
        DP[s_length] = True

        for i in range(s_length-1, -1, -1):
            for word in wordDict:
                word_length = len(word)

                # if reach to the end
                if i + word_length > s_length:
                    continue

                # if available, get True from above
                if s[i:i+word_length] == word:
                    DP[i] = DP[i+word_length]

                # we only need to check one case that True
                if DP[i] == True:
                    break
        
        return DP[0]