[코딩 테스트] 리트코드139 -Word Break (Medium) in Python

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

 

 

문자열 s와 문자열들의 집합 wordDict가 주어졌을 때, wordDict안의 단어로 s를 만들 수 있는 지 확인!

 

 

예시:

Input: s = "leetcode", wordDict = ["leet","code"]

Output: true

Explanation: Return true because "leetcode" can be segmented as "leet code".

 

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.

 

풀이

이 문제는  Discussion의 힘을 빌렸다.

 

풀이의 요지는

문자열 s의 각 문자에 T/F를 배정하는 배열을 만들고,
문자열 s의 각 문자를 돌면서,
그  문자로  끝나는 단어가 wordDIct에 있으면서 && 그 단어의 시작점에서 True였다면 True를 넣어주고,
답으로는 배열의 마지막 원소 값 - True / False를 반환하면 된다.

 

예를 들어 s가 "leetcode"이고, wordDict에 "leet"과 "code"가 있다면,

 

1) 초기화 된 배열

arr = [True (더미), False, False, False, False, False, False, False, False]

                         l         e      e       t      c       o      d       e

가 되고,

 

2) index = 4에서 wordDict 안에 있는 "leet" 문자가 끝나고,

"leet"의 시작점에 해당하는 index = 0번 노드의 값이 True이므로,

arr[4] = True로 고쳐준다.

 

arr = [True (더미), False, False, False, True, False, False, False, False]

 

3) 비슷한 논리로 "code"에 해당하는 부분도 고치면

 

arr = [True (더미), False, False, False, True, False, False, False, True] 

 

가 되고,

arr[-1] == True이기에 전체적 답은 True가 된다.

 

파이썬 구현

class Solution:
	def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False for i in range(n+1)]
        dp[0] = True
        
        for i in range(1,n+1): # 각 문자열의 문자에서
            for w in wordDict: # wordDict의 모든 문자열을 검사해줌
                if dp[i-len(w)] and s[i-len(w):i]==w: #문자열의 시작이 True이고 해당 문자열이 포함되면
                    dp[i]=True
        return dp[-1]

 

시간 복잡도는 O(n) * O(wordDict 길이) = O(n * m), 문제의 제한사항 바탕으로는 300 * 1000 = 300,000으로 1억보다 훨씬 적어 가능한 풀이가 된다.

제한 사항이 널널하게 주어졌기에 이중 중첩문으로 풀 수 있었다.