139. Word Break - Explanation

Description

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of dictionary words.

You are allowed to reuse words in the dictionary an unlimited number of times. You may assume all dictionary words are unique.

Example 1:

Input: s = "neetcode", wordDict = ["neet","code"]

Output: true

Explanation: Return true because "neetcode" can be split into "neet" and "code".

Example 2:

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

Output: true

Explanation: Return true because "applepenapple" can be split into "apple", "pen" and "apple". Notice that we can reuse words and also not use all the words.

Example 3:

Input: s = "catsincars", wordDict = ["cats","cat","sin","in","car"]

Output: false

Constraints:

1 <= s.length <= 200
1 <= wordDict.length <= 100
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of only lowercase English letters.

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n * m * t) time and O(n) space, where n is the length of the string s, m is the number of words in wordDict, and t is the maximum length of any word in wordDict.

Hint 1

Try to think of this problem in terms of recursion, where we explore all possibilities. We iterate through the given string s, attempting to pick a word from wordDict that matches a portion of s, and then recursively continue processing the remaining string. Can you determine the recurrence relation and base condition?

Hint 2

The base condition is to return true if we reach the end of the string s. At each recursive call with index i iterating through s, we check all words in wordDict and recursively process the remaining string by incrementing i by the length of the matched word. If any recursive path returns true, we immediately return true. However, this solution is exponential. Can you think of an optimization? Maybe you should consider an approach that avoids repeated work.

Hint 3

We can avoid recalculating results for recursive calls by using memoization. Since we iterate with index i, we can use a hash map or an array of the same length as s to cache the results of recursive calls and prevent redundant computations.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:

        def dfs(i):
            if i == len(s):
                return True

            for w in wordDict:
                if ((i + len(w)) <= len(s) and
                     s[i : i + len(w)] == w
                ):
                    if dfs(i + len(w)):
                        return True
            return False

        return dfs(0)

Time & Space Complexity

Time complexity: $O(t * m ^ n)$
Space complexity: $O(n)$

Where $n$ is the length of the string $s$ , $m$ is the number of words in $wordDict$ and $t$ is the maximum length of any word in $wordDict$ .

2. Recursion (Hash Set)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordSet = set(wordDict)

        def dfs(i):
            if i == len(s):
                return True

            for j in range(i, len(s)):
                if s[i : j + 1] in wordSet:
                    if dfs(j + 1):
                        return True
            return False

        return dfs(0)

Time & Space Complexity

Time complexity: $O( (n * 2 ^ n) + m)$
Space complexity: $O(n + (m * t))$

Where $n$ is the length of the string $s$ and $m$ is the number of words in $wordDict$ .

3. Dynamic Programming (Top-Down)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        memo = {len(s) : True}
        def dfs(i):
            if i in memo:
                return memo[i]

            for w in wordDict:
                if ((i + len(w)) <= len(s) and
                     s[i : i + len(w)] == w
                ):
                    if dfs(i + len(w)):
                        memo[i] = True
                        return True
            memo[i] = False
            return False

        return dfs(0)

Time & Space Complexity

Time complexity: $O(n * m * t)$
Space complexity: $O(n)$

Where $n$ is the length of the string $s$ , $m$ is the number of words in $wordDict$ and $t$ is the maximum length of any word in $wordDict$ .

4. Dynamic Programming (Hash Set)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordSet = set(wordDict)
        t = 0
        for w in wordDict:
            t = max(t, len(w))

        memo = {}
        def dfs(i):
            if i in memo:
                return memo[i]
            if i == len(s):
                return True
            for j in range(i, min(len(s), i + t)):
                if s[i : j + 1] in wordSet:
                    if dfs(j + 1):
                        memo[i] = True
                        return True
            memo[i] = False
            return False

        return dfs(0)

Time & Space Complexity

Time complexity: $O((t ^ 2 * n) + m)$
Space complexity: $O(n + (m * t))$

Where $n$ is the length of the string $s$ , $m$ is the number of words in $wordDict$ and $t$ is the maximum length of any word in $wordDict$ .

5. Dynamic Programming (Bottom-Up)

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

        for i in range(len(s) - 1, -1, -1):
            for w in wordDict:
                if (i + len(w)) <= len(s) and s[i : i + len(w)] == w:
                    dp[i] = dp[i + len(w)]
                if dp[i]:
                    break

        return dp[0]

Time & Space Complexity

Time complexity: $O(n * m * t)$
Space complexity: $O(n)$

Where $n$ is the length of the string $s$ , $m$ is the number of words in $wordDict$ and $t$ is the maximum length of any word in $wordDict$ .

6. Dynamic Programming (Trie)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True

    def search(self, s, i, j):
        node = self.root
        for idx in range(i, j + 1):
            if s[idx] not in node.children:
                return False
            node = node.children[s[idx]]
        return node.is_word

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        trie = Trie()
        for word in wordDict:
            trie.insert(word)

        dp = [False] * (len(s) + 1)
        dp[len(s)] = True

        t = 0
        for w in wordDict:
            t = max(t, len(w))

        for i in range(len(s), -1, -1):
            for j in range(i, min(len(s), i + t)):
                if trie.search(s, i, j):
                    dp[i] = dp[j + 1]
                    if dp[i]:
                        break

        return dp[0]

Time & Space Complexity

Time complexity: $O((n * t ^ 2) + m)$
Space complexity: $O(n + (m * t))$

Where $n$ is the length of the string $s$ , $m$ is the number of words in $wordDict$ and $t$ is the maximum length of any word in $wordDict$ .