139. Word Break 풀이

leetcode.com/problems/word-break/

Word Break - LeetCode

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        
        if not s or not wordDict :
            return False
        
        words = set(wordDict)
        n = len(s)
        
        dp = [False]*(n+1)
        dp[0] = True
        
        for end in range(1, n+1) :
            for start in range(n) :
                if dp[start] and s[start:end] in words :
                    dp[end] = dp[start]
                    break

        return dp[-1]
    

정리 :

처음 접근 방법은 위의 풀이와 비슷하지만 start를 바깥 for문에 선언하고 end를 안쪽 for문에 선언을 했다. end 루프를 바깥에 쓸때 좋은 점은 s[start:end]를 단어장에서 발견했을 때 안에 있는 for문을 바로 종료시킬 수 있기 때문.