leetcode 139. Word Break

정답 소스

 

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:

        # ex) s : leetcode
        # s[0:7]
        n = len(s)
        print(s[7])
        #dp[0:8]
        dp = [i==0 for i in range(n+1)]
        
        # i : 0 ~ 8
        for i in range(n+1):
            # j : 0 ~ 7(max)
            for j in range(i):
                if dp[j] == True and s[j:i] in wordDict:
                    dp[i] = True
                    break
        return dp[-1]

 

 

 

문제 해결 idea

dict의 단어 조합으로 만들어 질 수 있는 문자열 S의 subword를 2중 for문으로 찾고,

찾은 index+1의 dp 값을 dp[index+1] = True로 표기하여 dp[] 리스트에서 특정 index의 값이 True로 되어 있다면 그 이전 subword들은 dict의 단어 조합으로 만들 수 있다고 판단하는 방법이다.

 

ex: 아래 단어에서 leet를 먼저 찾은 경우 dp 값의 변화

S = leetcode

dp = [False,False,False,False,False,False,False,False,False]

 

위 상태에서 leet 단어를 찾은 경우(s[0:4]) dp 리스트의 변화 (i:4, j:0 일 때)

dp[4] = True

dp = [False,False,False,False,True,False,False,False,False]

 

위 상태에서 code 단어를 찾은 경우(s[4:8]) dp 리스트의 변화 (i:8, j:4 일 때)

dp[8] = True

dp = [False,False,False,False,True,False,False,False,True]

 

 

dp 리스트에서 문자열 리스트 S의 마지막 인덱스+1 의 값이 True라면 (dp[len(s)] == True), wordDict의 구성요소 단어들로 문자열 S를 만들 수 있음을 알 수 있고 True 값을 return한다.

 

하지만 만들 수 없다면 False를 return하게 된다.