[LeetCode 풀이/python] 139. Word Break (medium)

문제 설명: 문자열 s 와 문자열 사전 wordDict 가 주어졌을 때, 사전에 포함된 하나 이상의 단어로 이루어지며 각 단어가 띄어쓰기로 구분되는 시퀀스로 s 가 분해될 수 있으면 true 를 리턴하시오. 참고로 사전에 포함된 각 단어는 분해 과정에서 여러 번 사용될 수 있다.

(Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.)

 

 

예시 1)

입력: s = "leetcode", wordDict = ["leet","code"]  -->  출력: true

설명: 문자열 "leetcode" 는 leet  code 로 분해될 수 있다

 

예시 2)

입력: s = "applepenapple", wordDict = ["apple","pen"]  -->  출력: true

설명: 문자열 "applepenapple" 은 apple  pen  apple 로 분해될 수 있다

 

예시 3)

입력: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]  -->  출력: false

 

제한 조건:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s 와 wordDict[i] 는 영문 소문자로만 이루어져 있다
• wordDict 의 모든 문자열은 중복되지 않고 유일하다(unique)

 

------ * ------ * ------ * ------

 

[풀이 1안]  -- w/ solution peeping

• 접근법
  • Dynamic Programming 을 이용하여, 문자열 s 의 i 번째 문자까지에 해당하는 문자열 s[:i] 가 분해 가능하면 dp[i] = True(1) 를, 불가능하면 False(0) 를 저장한다
  • 0 <= j < i 일 때, i 에 선행하는 j 까지의 문자열 s[:j] 이 분해 가능하고 (dp[j] == True) & j+1 번째부터 i 번째 문자까지로 이루어진 단어가 사전 wordList 에 존재하면 s[:i] 은 분해 가능하다고 할 수 있음
    • i 에 선행하는 인덱스 j 를 wordList 의 각 word 를 이용해서 역산하여 구하는 것이 포인트.....!
    • 처음에는 이렇게 True 가 되는 경우에 대해 선행 인덱스를 dp[i] 값에 저장하는 식으로 구현해보려고 했었음 @_@ (는 fail...) 

 

• 코드 구현

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    dp = [ 0 for _ in range(len(s)+1) ]
    dp[0] = 1
    wordDict = set(wordDict)
        
    for i in range(1, len(dp)):
        for word in wordDict:
            if (dp[i-len(word)]) and (s[i-len(word):i] == word):
                dp[i] = 1
                    
    if dp[-1]: return True
    else: return False

 

• 결과
  • 생각보다 아름답고 간결한 코드...!
  • 문자열 s 의 길이를 n, 사전 wordDict 의 크기를 m 이라 할 때, O(n) * O(m) = O(n*m) 의 시간 복잡도를 가짐