139. Word Break

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

Example

---

Input: s = “leetcode”, wordDict = [“leet”,”code”]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.
💡 Note that you are allowed to reuse a dictionary word.

💻 Code

Approach : We only need to iterate s once, and wordDict should be checked at the same time.

Things to be considered :

• Strings in the wordDict can be used multiple times.
• Unique strings.
• Matching strings in s cannot be overlapped.

1. Dynamic Programming

---

• TC : O(n * m)
  • n : length of s
  • m : max length of wordDict
• SC: O(n) - dp

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # All the strings of wordDict are unique.
        wordSet = set(wordDict)

        # checking strings connected w/o overlapping
        # true .... true -> it makes a single string that in twordDict
        dp = [False] * (len(s) + 1)
        dp[0] = True 

        for i in range(1, len(s) + 1):
            for j in range(i):
                # dp[j] picks up where we left off last time
                # until it matches
                if dp[j] and s[j:i] in wordSet: 
                    dp[i] = True
                    break
        
        # return if the last index is true
        return dp[len(s)]

Using DP to track whether the current position of s is the part of the strings in wordDict allows an intuitive result because of the dp table.
Check below the short version of dp table in processing:

                      l      e      e      t      c      o      d      e
        -------------------------------------------------------------------
        dp = [True, False, False, False, False, False, False, False, False]
        dp = [True, False, False, False, True, False, False, False, False]
        dp = [True, False, False, False, True, False, False, False, True]
            => dp[len(s)] = True
            It checks only if the last index is True

2. DFS

---

• TC : O(n^2)
• SC: O(n)

  class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        visited = {}
        wordSet = set(wordDict)
  
        def dfs(s, wordSet, visited):
            if s in visited:
                return visited[s]
            if s in wordSet:
                return True
  
            for i in range(1, len(s)):
                prefix = s[:i]
                if prefix in wordSet and dfs(s[i:], wordSet, visited):
                    visited[s] = True
                    return True
          
            visited[s] = False
            return False
  
        return dfs(s, wordSet, visited)
  

  The code processing:

    Initial call: dfs("leetcode")
        Check prefix "l", not in wordSet.
        Check prefix "le", not in wordSet.
        Check prefix "lee", not in wordSet.
        Check prefix "leet", in wordSet.
            Recursive call: dfs("code")
                Check prefix "c", not in wordSet.
                Check prefix "co", not in wordSet
                Check prefix "cod", not in wordSet
                Check prefix "code", in wordSet
                    Memoize and return True for "code".
            Memoize and return True for "leetcode"