[LC] 139. Word Break

[seungriyou]

https://leetcode.com/problems/word-break/

Approach

어려워서 solution 참고 ㅎㅎ editorial도 참고하자.. ㅠ (BFS 풀이 방법도 있음)

Idea 1: DP

뒤에서부터 확인해가며 결과를 완성하는 방향으로 접근한다. (dp 테이블을 채워나갈 때 어디서부터 채워나가야 할지 잘 생각해보자!)

• top-down

  • @cache(@lru_cache(None))를 이용하여 memoization을 활용한다.
  • start의 다음 index 값부터 end로 확인하며, (1) wordDict에 s[start:end]가 있고 (2) dp(end)가 True라면 True를 반환하도록 한다.
  • base condition은 start == len(s)일 때이며, 이때는 True를 반환하도록 한다.

• bottom-up

  • dp[i] = s[i:]가 wordDict의 원소로 구성될 수 있는지 여부
  • base condition은 dp[len(s)] = True로 설정한다.
  • start는 len(s) - 1에서부터 거꾸로 순회하고, end는 start + 1부터 len(s)까지 순회한다.
  • top-down과 마찬가지로 (1) dp[end]가 True이고 (2) wordDict에 s[start:end]가 있으면 dp[start]를 True로 기록한다.

Idea 2: DP + Trie

bottom-up 방식 DP에 trie를 적용해보자.

모든 word를 trie로 구축하여 사용하면 s[start:end]가 wordDict에 존재하는지 확인하는 과정을 O(1)으로 최적화 할 수 있다.

하지만 실제로 제출했을 때 딱히 runtime이 유의미하게 줄어드는 것 같지는 않다..?

이유가 뭐지? t(= wordDict 내 모든 문자 개수)가 너무 커서일까?

• 일반 bottom-up DP (space 측면에서는 확실히 더 낫다)

  def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    """bottom up"""
  
    n = len(s)
    words = set(wordDict)   # -- O(m)
  
    # dp[i] = s[i:]가 wordDict의 word로 구성될 수 있는지 여부
    dp = [False] * (n + 1)
    dp[n] = True
  
    for start in range(n - 1, -1, -1):
        for end in range(start + 1, n + 1):  # -- O(n^2)
            # (1) dp[end]가 True이고 (2) wordDict에 현재 찾고 있는 word가 있다면
            if dp[end] and s[start:end] in words:  # -- O(n)
                dp[start] = True
                break
  
    return dp[0]

• bottom-up DP + trie

  class TrieNode:
    def __init__(self):
        self.is_word = False
        self.child = defaultdict(TrieNode)
  
    def add_word(self, word):
        curr = self
  
        # word의 문자들을 타고 내려가기
        for c in word:
            curr = curr.child[c]
  
        # 단어가 완료됨을 표시하기
        curr.is_word = True

  def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    """bottom up & trie"""
  
    # trie 구성하기 -- O(t)
    root = TrieNode()
    for word in wordDict:
        root.add_word(word)
  
    n = len(s)
  
    # dp[i] = s[i:]가 wordDict의 word로 구성될 수 있는지 여부
    dp = [False] * (n + 1)
    dp[n] = True
  
    for start in range(n - 1, -1, -1):
        curr = root
        for end in range(start + 1, n + 1): # -- O(n^2)
            c = s[end - 1]
  
            # c가 curr.child에 없다면 중단
            if c not in curr.child:
                break
  
            # c가 curr.child에 있다면 타고 내려가기
            curr = curr.child[c]
  
            # (1) word가 완성됐고 (2) dp[end]가 True이면
            if curr.is_word and dp[end]:
                dp[start] = True
                break
  
    return dp[0]

Complexity

• Time: (DP) O(n^3 + m) (n = len(s), m = len(wordDict)) / (DP + Trie) O(n^2 + t) (t = wordDict 내 모든 문자 개수)
• Space: (DP) O(n + m) / (DP + Trie) O(n + t)