139.Word_Break_(Medium).md

139. Word Break (Medium)

Date and Time: Jul 2, 2024, 16:01 (EST)

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

Question:

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.

Example 1:

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

Output: true

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

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]

Output: true

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

Output: false

Example 4:

Input: s = "cars", wordDict = ["car", "ca", "rs"]

Output: true

Example 5:

Input: s = "aaaaaaa", wordDict = ["aaaa", "aaa"]

Output: true

Example 6:

Input: s = "goalspecial", wordDict = ["go", "goal", "goals", "special"]

Output: true

KeyPoints:

We want to create dp = [False] * (len(s) + 1), and we want to check backward from s to see if word in wordDict matches. So we first set dp[len(s)] = True, then we loop from the last index of s to the first index, and we check if current index i + len(word) <= len(s) and s[i:i+len(w)] == w, so we can make sure the word we really want is in s.

After we found the word, we set dp[i] = dp[i+len(w)] to see if the previous word we found + current word we found is exactly s, if yes, we can break to move index i forward.

Finally, we can just return dp[0].

My Solution:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # Store dp backward
        # s = "leetcode", dp = [F, F, F, F, F, F, F, F, T]
        dp = [False] * (len(s) + 1)
        dp[len(s)] = True
        for i in range(len(s)-1, -1, -1):
            for w in wordDict:
                # Check word in bound and word is the same in s
                if i + len(w) <= len(s) and s[i:i+len(w)] == w:
                    dp[i] = dp[i+len(w)]  # s.index(c) + len(word) = dp[8] = True
                # If dp[i] is True, we can decrement i to check next word
                if dp[i]:
                    break
        return dp[0]

Time Complexity: $O(n * m)$, where n = len(s), m = len(wordDict).
Space Complexity: $O(n)$