[LeetCode] 139. Word Break

링크

문자열 s와 단어 사전인 wordDict가 있다.

s는 wordDict안에 있는 단어들로 만들 수 있으면 True 없으면 False를 리턴하는 문제

제약사항

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20

첫 번째 아이디어

DFS로 모든 단어를 검사하자

def dfs(prefix):  
    for i in range(1, len(prefix)):  
        if prefix[:i] in wordDict:  
            suffix = prefix[i:]  
            if suffix in wordDict or dfs(suffix):  
                return True  
    return False  

if dfs(s) or s in wordDict:  
    print(True)  
else:  
    print(False)

시간초과가 났다.
아직 시간복잡도가 어렵다 ㅠㅠ

두번째 아이디어

1. s길이만큼 bool배열을 만든다.
2. for문을 s의 길이만큼 돌린다.
3. 여기서 단어와 s를 비교한다. 그리고 만약 단어와 s가 같다면 s바로 앞 배열이 참인지 확인한다. 그런데 첫번째 단어일 경우 바로 앞 배열은 -1이 되므로 첫번째 인지 확인 후 첫번째 단어라면 참으로 한다.
4. for문이 다 돌고난 후 bool배열의 마지막 위치가 참인지 거짓인지 확인하여 리턴한다.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        d = [False] * len(s)
        for i in range(len(s)):
            for word in wordDict:
                if word == s[i - len(word) + 1 : i + 1] and (d[i - len(word)] or i - len(word) + 1 == 0):
                    d[i] = True

        return d[-1]

굿