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:
- In a recursive function, we check if the current substring is present in the dictionary, if yes return True.
- 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.
- 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 returnTrue
. - If no valid segmentation is found, we store the result (
False
) in our memo for the current substring and returnFalse
.
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#.
- An array or dictionary
dp
(namedmemo
in the solutions) is used to store the computed intermediate results.dp[i]
(ormemo[s[i:]]
) contains whether the substrings[0..i-1]
can be segmented into dictionary words. - An outer loop from 0 to N is used for computing
dp[i]
. - 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] isTrue
, dp[i] will be setTrue
. - Both current substring and the other part are valid then mark current substring as valid in memo.
- The substring
- If the entire string is segmented with dictionary words,
dp[s.length]
(ormemo[s]
) would beTrue
consequently.
JavaScript: The dynamic programming approach is implemented similarly in JavaScript.
set
is used for quick lookup of the words, created bynew Set(wordDict)
.- Similarly to the Python solution,
dp[0]
is set toTrue
. - The outer loop from 1 to N+1, inclusive, is used for computing
dp[i]
. - The inner loop from 0 to i is used for finding a valid segmentation.
- If
dp[j]
isTrue
and the substrings.substring(j, i)
is a dictionary word, thendp[i]
is set toTrue
, and the inner loop breaks.
- If
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.