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:trueExplanation:"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 till0th indexedcharacter:"w"Start an inner loop from index0 to 0 characterof input. result[0] ("") is true. Remaining is "w". But "w" is not present in dictionary. Inner loop ends.result: [true, false]

Substring tillindex 1character:"we"Start inner loop from index0 to 1of 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 tillindex 2character:"wel"Start inner loop from index0 to 2of 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 tillindex 3character:"weli"Start inner loop from index0 to 3of 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 tillindex 4character:"welik"Start inner loop from index0 to 4of 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 tillindex 5character:"welike"Start inner loop from index0 to 5of 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()]; }}`