139. Word Break

Description

The wordBreak function determines if a string s can be segmented into one or more words from a given dictionary wordDict. The dictionary contains a list of valid words.

Intuition

To solve the problem, we need to check if the string s can be divided into a sequence of words that all exist in the dictionary. We use a backtracking approach combined with memoization to efficiently explore and remember previously computed results.

Approach

1. Initialization: Convert the wordDict list into a set for efficient lookup operations. Initialize a memoization dictionary to store results of subproblems.
2. Backtracking Function: - Parameters: - v: The current word being formed. - i: The current index in the string s. - Base Case: If the end of the string s is reached, check if the remaining part of v is empty. If so, return True. - Recursive Case: - If v + s[i] forms a valid word in the dictionary, recursively check if the rest of the string starting from the next index can also be segmented. - If not, continue to build v by adding the current character s[i] and check the remaining substring.
3. Memoization: - Cache results of previously computed subproblems to avoid redundant computations. - Use a key derived from the current index and the length of the current word v to store and retrieve results from the memoization dictionary.

Complexity

Time Complexity:

The worst-case time complexity is exponential due to the recursive exploration of all possible segmentations of the string. Memoization helps reduce redundant calculations.

Space Complexity:

O(n) for the memoization dictionary and the recursion call stack, where n is the length of the string s.

Code

C++

class Solution {
public:
    bool wordBreak(string s, vector& wordDict) {
        unordered_set dict(wordDict.begin(), wordDict.end());
        unordered_map visited;
        
        function backtrack = [&](string v, int i, string visitedKey) -> bool {
            if (i == s.size()) return v.empty();
            visitedKey = to_string(i - v.size()) + "_" + to_string(i);
            if (visited.find(visitedKey) != visited.end()) return visited[visitedKey];
            bool res = false;
            if (dict.find(v + s[i]) != dict.end()) res = backtrack("", i + 1, visitedKey);
            if (!res) res = backtrack(v + s[i], i + 1, visitedKey);
            visited[visitedKey] = res;
            return res;
        };

        return backtrack("", 0, "");
    }
};

Python

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dict_set = set(wordDict)
        visited = {}
        def backtrack(v="", i=0):
            if i == len(s):
                return v == ""
            visited_key = f"{i - len(v)}_{i}"
            if visited_key in visited:
                return visited[visited_key]
            
            res = False
            if v + s[i] in dict_set:
                res = backtrack("", i + 1)
            if not res:
                res = backtrack(v + s[i], i + 1)
                
            visited[visited_key] = res
            return res
        return backtrack()

Java

class Solution {
    public boolean wordBreak(String s, List wordDict) {
        Set dict = new HashSet<>(wordDict);
        Map visited = new HashMap<>();

        return backtrack(s, dict, "", 0, visited);
    }
    private boolean backtrack(String s, Set dict, String v, int i, Map visited) {
        if (i == s.length()) return v.isEmpty();
        String visitedKey = (i - v.length()) + "_" + i;
        if (visited.containsKey(visitedKey)) return visited.get(visitedKey);
        boolean res = false;
        if (dict.contains(v + s.charAt(i))) res = backtrack(s, dict, "", i + 1, visited);
        if (!res) res = backtrack(s, dict, v + s.charAt(i), i + 1, visited);
        visited.put(visitedKey, res);
        return res;
    }
}

JavaScript

var wordBreak = function(s, wordDict) {
    const dict = new Set(wordDict);
    const backtrack = (v="",i=0, visited = new Map())=>{
        if(i==s.length) return v=="";
        if(visited.has((i-v.length)+"_"+i)) return visited.get((i-v.length)+"_"+i);
        let res = false;
        if(dict.has(v+s[i])) res = backtrack("",i+1,visited);
        if(!res) res = backtrack(v+s[i],i+1,visited);
        visited.set((i-v.length)+"_"+i, res);
        return res;
    }
    return backtrack();
    
};