[코딩 인터뷰][LeetCode] – Word Break

해당 포스트는 LeetCode의 코딩 인터뷰 문제 Word Break에 대한 풀이입니다. 해당 풀이는 Optimal이 아닌 단순히 Submission을 통과한 것입니다.

문제 정보

문제 출처 : https://leetcode.com/problems/word-break/
카테고리 : DP
난이도 : 쉬움 ~ 어려움 (풀이에 따라서 다름)

---

문제 설명

주어진 문자열 s를 dict내의 문자들을 조합해서 만들 수 있는지 여부를 출력하시오.
예) s = “wordbreak”이고 dict = [“word”, “break”]이면 True를 출력한다.
예) s = “wordbreakword”이고 dict = [“word”, “break”]이면 True를 출력한다.
예) s = “wordbreaks”이고 dict = [“word”, “break”]이면 False를 출력한다.

---

문제 풀이

이 문제의 풀이를 위해 Boolean 배열 Visited를 사용한다. visited[i]는 s[0 : i]의 부분 문자열을 dict내의 문자들을 조합해서 만들 수 있다는 것을 의미한다. s의 길이를 N이라고 할 때, i를 0에서 N – 1까지 iteration 시킨다.

visited[i]가 0인 경우 s[0 : i]까지의 부분 문자열은 이미 완성되었으므로, 그 다음으로 붙일 수 있는 것을 찾는다. dict내의 단어 word에 대해 word가 s[i : i + len(word)]와 같으면 그 뒤에 이어붙일 수 있다. 그렇다면 visited[i + len(word)]에 True를 할당한다.

for loop문이 끝난 후에 visited[N + 1]을 리턴하면 된다.

※ KMP 알고리즘을 사용하면 위 풀이를 더 발전시킬 수 있다. KMP 알고리즘으로 각 word가 s에 출현하는 위치 i를 찾아낸다. 이 연산의 속도는 O(len(s) + len(word))이다. match는 set의 배열로, match[i]는 s[i : i + len(word)] == word인 word들의 길이를 저장하는 set이다. 기존 풀이의 for loop에서 각 i에 대해서 match[i]의 값들을 참조해 visited를 채워나가면 매번 s[i + len(word)]와 word를 비교하는 낭비를 없앨 수 있다.

---

코드

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        visited = [0] * (len(s) + 1)
        visited[0] = True
        length = len(s)
        for i in range(length):
            if not visited[i]:
                continue
            for word in wordDict:
                if len(word) <= length - i and word == s[i:i + len(word)]:
                    visited[i + len(word)] = True
        return visited[length]