Leetcode 139. Word Break

Problem Explanation

In this problem, we need to check if the given string can be segmented into a space-separated sequence of one or more dictionary words. Each word from the dictionary can be used multiple times.

For Example, consider string s = "leetcode" and dictionary wordDict = ["leet", "code"]

Here, the string "leetcode" can be segmented as "leet code" where "leet" and "code" are the words from the dictionary. So, in this case, the function should return True.

Approach to the solution is to use recursion along with memoization to reduce time complexity:

1. In a recursive function, we check if the current substring is present in the dictionary, if yes return True.
2. If the current substring is not present in the dictionary, we check if the function has been already evaluated for the current substring in our memo. If already computed, then return the result stored in the memo.
3. If step 1 and step 2 are not met, then, for each substring, we find all possible prefixes and check if the prefix is present in the dictionary using the count method. After that, we recursively call the function for the remaining substring (suffix). If both prefix and recursive call for suffix return True, then we have found a valid segmentation, so we store the result (True) in our memo for the current substring and return True.
4. If no valid segmentation is found, we store the result (False) in our memo for the current substring and return False.

Python Solution:

1
2python
3class Solution:
4    def wordBreak(self, s, wordDict):
5        def word_Break(s, wordDict, memo):
6            if s in wordDict:return True
7            if s in memo:return memo[s]
8            for i in range(1, len(s)):
9                if s[:i] in wordDict and word_Break(s[i:], wordDict, memo):
10                    memo[s] = True
11                    return memo[s]
12            memo[s] = False
13            return memo[s]
14        return word_Break(s, set(wordDict), {})
15

Java Solution:

1
2java
3class Solution {
4    public boolean wordBreak(String s, List<String> wordDict) {
5        return wordBreak(s,new HashSet(wordDict), new HashMap<String, Boolean>());
6    }
7
8    private boolean wordBreak(String s, HashSet<String> wordSet,HashMap<String, Boolean> memo) {
9        if(wordSet.contains(s))return true;
10        if(memo.containsKey(s))return memo.get(s);
11        
12        for(int i = 1; i < s.length();i++){
13            String prefix = s.substring(0, i);
14            String suffix = s.substring(i);
15            
16            if(wordSet.contains(prefix) && wordBreak(suffix, wordSet, memo)){
17                memo.put(s, true);
18                return true;
19            }
20        }
21        
22        memo.put(s, false);
23        return false;
24    }
25}

C++ Solution:

1
2c++
3#include<bits/stdc++.h>
4using namespace std;
5
6class Solution {
7public:
8    bool wordBreak(string s, vector<string>& wordDict) {
9    static string ss;
10    static vector<string> wws;
11    static unordered_map<string,bool> umap;
12    static unordered_set<string> uset(wordDict.begin(),wordDict.end());
13    if(uset.find(s)!=uset.end())
14         return true;
15    if(umap.find(s)!=umap.end())
16         return umap[s];
17    for(int i=1;i<s.length();i++)
18    {
19         if(uset.find(s.substr(0,i))!=uset.end()&&wordBreak(s.substr(i),wordDict))
20         {
21              return umap[s]=true;
22         }
23    }
24    return umap[s]=false;
25    }
26};

C# Solution:

1
2csharp
3public class Solution {
4    private Dictionary<string, bool> memo = new Dictionary<string, bool>();
5
6    public bool WordBreak(string s, IList<string> wordDict) {
7        return Word_Break(s, new HashSet<string>(wordDict), 0, memo);
8    }
9
10    public bool Word_Break(string s, HashSet<string> wordDict, int start, Dictionary<string, bool> memo) {
11        if (start == s.Length) {
12            return true;
13        }
14        if (memo.ContainsKey(s.Substring(start))) {
15            return memo[s.Substring(start)];
16        }
17        for (int end = start + 1; end <= s.Length; end++) {
18            if (wordDict.Contains(s.Substring(start, end - start)) && Word_Break(s, wordDict, end, memo)) {
19                memo[s.Substring(start)] = true;
20                return true;
21            }
22        }
23        memo[s.Substring(start)] = false;
24        return false;
25    }
26}

JavaScript Solution:

1
2javascript
3var wordBreak = function(s, wordDict) {
4    let dp = [];
5    let set = new Set(wordDict);
6    dp[0] = true;
7    
8    for(let i=1;i<=s.length;i++){
9        for(let j=0;j<i;j++){
10            if(dp[j]&&set.has(s.substring(j,i))){
11                dp[i] = true;
12                break;
13            }
14        }
15    }
16    return dp[s.length]===true;
17};

This problem is a typical dynamic programming problem involving strings. Let's further analyze how these solutions work.

Python/Java/C++/C#: The dynamic programming approach is implemented in Python, Java, C++, and C#.

1. An array or dictionary dp (named memo in the solutions) is used to store the computed intermediate results. dp[i] (or memo[s[i:]]) contains whether the substring s[0..i-1] can be segmented into dictionary words.
2. An outer loop from 0 to N is used for computing dp[i].
3. An inner loop from 0 to i is used for segmenting the string into two substrings.
   • The substring s[j..i-1] (s[j, i] in Python) is a valid word and dp[j] is True, dp[i] will be set True.
   • Both current substring and the other part are valid then mark current substring as valid in memo.
4. If the entire string is segmented with dictionary words, dp[s.length] (or memo[s]) would be True consequently.

JavaScript: The dynamic programming approach is implemented similarly in JavaScript.

1. set is used for quick lookup of the words, created by new Set(wordDict).
2. Similarly to the Python solution, dp[0] is set to True.
3. The outer loop from 1 to N+1, inclusive, is used for computing dp[i].
4. The inner loop from 0 to i is used for finding a valid segmentation.
   • If dp[j] is True and the substring s.substring(j, i) is a dictionary word, then dp[i] is set to True, and the inner loop breaks.
5. dp[s.length] holds the result for the entire string, hence it is returned as the result.

The dynamic programming approach allows solving the problem in O(N^2) time complexity due to the two nested loops, and O(N) space complexity for the dynamic programming array. Compared to the naive approach of trying all possible segmentations, which has exponential time complexity, the dynamic programming approach is much more efficient.