We will solve LeetCode problem “139. Word Break” here. The problem statement is as below:
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.
Input: s = "welike", wordDict = ["we", "like", "foot", "ball"] Output: true Explanation: "welike" can be segmented as "we like". So output is true.
We will solve this Word Break problem using dynamic programming approach. How does that help? Let’s consider the example above & find the solution step by step.
We will create a new result array variable. Result array size would be n + 1 where n is the input size. It is a boolean array. Boolean status of a particular index will tell us whether word break is possible till that position from the starting character.
Base case is when input is empty (“”). That can be represented with dictionary words as there is nothing to represent.
So result[0] = true.
Start a loop from 0th indexed character of given input:
Substring till 0th indexed character: "w"
Start an inner loop from index 0 to 0 character of input.
result[0] ("") is true. Remaining is "w". But "w" is not present in dictionary.
Inner loop ends.
result: [true, false]
Substring till index 1 character: "we"
Start inner loop from index 0 to 1 of input.
result[0] ("") is true. Remaining is "we". "we" is present in dictionary. So result[2] = true.
We have found match. So we can break the inner loop.
Inner loop ends.
result: [true, false, true]
Substring till index 2 character: "wel"
Start inner loop from index 0 to 2 of input.
result[0] ("") is true. Remaining is "wel". "wel" is not present in dictionary.
result[1] ("w") is false. So there is no point checking if remaining "el" is present in dictionary.
result[2] ("we") is true. Remaining "l" is not present in dictionary.
Inner loop ends.
result: [true, false, true, false]
Substring till index 3 character: "weli"
Start inner loop from index 0 to 3 of input.
result[0] ("") is true. Remaining "weli" is not present in dictionary.
result[1] ("w") is false. So there is no point checking if remaining "eli" is present in dictionary.
result[2] ("we") is true. Remaining "li" is not present in dictionary.
result[3] ("wel") is false. So we can skip checking remaining part.
Inner loop ends.
result: [true, false, true, false, false]
Substring till index 4 character: "welik"
Start inner loop from index 0 to 4 of input.
result[0] ("") is true. Remaining "welik" is not present in dictionary.
result[1] ("w") is false. We can skip checking remaining part.
result[2] ("we") is true. Remaining "lik" is not present in dictionary.
result[3] ("wel") is false. So we can skip checking remaining part.
result[4] ("weli") is false. We don't need to check remaining part.
Inner loop ends.
result: [true, false, true, false, false, false]
Substring till index 5 character: "welike"
Start inner loop from index 0 to 5 of input.
result[0] ("") is true. Remaining "welike" is not present in dictionary.
result[1] ("w") is false. We can skip checking remaining part.
result[2] ("we") is true. Remaining "like" is present in dictionary.
We have found match. So we can break the inner loop.
Inner loop ends.
result: [true, false, true, false, false, false, true]
We have reached the end of input. And result[n] = true. So the input can be segmented to words using the given dictionary.
I hope you have understood the basic concept of using dynamic programming here. We are using bottom-up approach of dynamic programming. We start with smaller sub-problem. Here we are checking if substring of the given input is breakable in words. That is the smaller problem. We use that to check if input itself is breakable in words or not. If a smaller sub-problem is true, we check if remaining part is already present in dictionary or not. That’s all. This way we can have a time complexity of O(n ^ 2) for the solution. We are using n + 1 extra space for the result array. So space complexity of this solution is O(n).
The complete Java code solution for above LeetCode problem is given below.
class Solution { public boolean wordBreak(String s, List<String> wordDict) { boolean[] result = new boolean[s.length() + 1]; //for empty string wordbreak is true result[0] = true; for(int i=0; i<s.length(); i++){ for(int j=0; j<=i; j++){ if(result[j] && wordDict.contains(s.substring(j,i+1))){ result[i+1] = true; break; } } } return result[s.length()]; }}