♒139. Word Break

Medium | Grind 75 | February 21 Tuesday, 2023

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.

Constraints:

• 1 <= s.length <= 300

• 1 <= wordDict.length <= 1000

• 1 <= wordDict[i].length <= 20

• s and wordDict[i] consist of only lowercase English letters.

• All the strings of wordDict are unique.

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

SOLUTION

We will use dynamic programming to solve this problem. We define a list dp of boolean values such that dp[i] represents whether the substring s[i:] starting from index i can be segmented into valid words from the word dictionary. We initialize the dp[len(s)] as True because an empty string can always be segmented.

Once the dp is set up, we iterate over all the possible suffixes of s starting from the end and moving to the beginning. For every suffix, we check if any of the words in the word dictionary can be used to form the current suffix. If so, we update the dp value for the index to True. Note that for instance, when the suffix is 6 characters long and the current word in the dictionary is four characters. Even if the current word can form the first four letters of the suffix, we need to check if any of the words were able to form the last two characters previously. Therefore, the way we update dp is based on the dp at index len(word)+current length of the suffix.

Finally, once we iterated over every suffix, we return the dp[0] value which represents whether the entire string s can be segmented into valid words from the dictionary.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False for i in range(len(s)+1)]
        dp[len(s)] = True

        # get every suffix of s
        for i in range(len(s), -1, -1): 
            # for every suffix of s, need to check if any word can form it
            for word in wordDict: 
                if len(word)+i <= len(s) and word == s[i:i+len(word)]: 
                    dp[i] = dp[i+len(word)]
                    # if current suffix can be formed, no need to look for other words
                    if dp[i]: break

        # dp[0] represents the entire string
        return dp[0]

TIME AND SPACE COMPLEXITY

TIME: O(n*m*k) where n is the length of string s, m is the number of words in the word dictionary, and k is the length of the longest word in the word dictionary. We iterate over every character in the strings s once. Within each iteration, we check every word in the word dictionary to see if the suffix can be formed by the word. The suffix and word comparison will at most take k times.

SPACE: O(n) where n is the length of string s. We create our dp of length n.

**Written with help from ChatGPT