# Word Break Problem

Leetcode: Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaceGiven a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words..

Return all such possible sentences.

For example, given

`s = "catsanddog"`

`dict = ["cat", "cats", "and", "sand", "dog"].`

`returns true`

The problem can be solved using Dynamic Programming. 1. Start traversing the string from index 0. At index 0 , substring 'c' is not in dict.
2. Substring `ca` is not in dict
3. Substring `cat` is in dict. Now there is two possibility as it can be seen in the diagram. consider `cat` as part of answer and traverse forward with substring `sanddog` and ignore `cat` and look for next substring which is `cats`.
4. Follow above steps till the end of the string. If by the end of string, it can be split into multiple words then return true

Note: If we follow above approach then same subproblems will be evaluated multiple times. This can be avoided by mapping out the iteration on a 2d array.

1. Create boolean 2d array of size mat[n][n]
2. Start a for loop `l = 1...n`. The value of l defines the length of the prefix
3. Start from `i=0... s.length()-l+1` and set value of `j= i+l-1`
4. Get substring of length `i..j`. If the substring is present in dict mark `mat[i][j] = true`
5. If the prefix is present in the dict mark `mat[i][j]=true`
6. if not then for `k=i..j` set `mat[i][j] = true if mat[i][k]=true && mat[k][j] = true`
7. After iterating through all prefixes return `mat[n-1]`
``````public class WordBreak {

public static void main(String[] args) {
List dict = new ArrayList<>();
System.out.println(new WordBreak().wordbreak("catsanddog", dict));
}

public boolean wordbreak(String words, List dict) {
boolean mat[][] = new boolean[words.length()][words.length()];

//initialize matrix
for (int i = 0; i < words.length(); i++)
mat[i][i] = dict.contains(words.charAt(i)+"");

for (int l = 2; l <= words.length(); l++) {
for (int i = 0; i < words.length() - l + 1; i++) {
int j = i + l - 1;
if (dict.contains(words.substring(i, j+1))) {
mat[i][j] = true;
continue;
}
for (int k = i; k < j; k++) {
if (mat[i][k] == true && mat[k+1][j] == true) {
mat[i][j] = true;
continue;
}
}
}
}
return mat[words.length() - 1];
}
}``````

The time complexity of above solution is `O(n^3)`. This can be optimized to `O(n^2).`

``` public class Solution { public boolean wordBreak(String s, List<String> wordDict) { boolean[] f = new boolean[s.length() + 1]; f = true; for (int i = 1; i <= s.length(); i++) { for (int j = 0; j<i; j++) { if (f[j] && wordDict.contains(s.substring(j, i))) { f[i] = true; break; } } } return f[s.length()]; } }```
``` var disqus_shortname = 'java-questions'; (function() { var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true; dsq.src = 'https://' + disqus_shortname + '.disqus.com/embed.js'; (document.getElementsByTagName('head') || document.getElementsByTagName('body')).appendChild(dsq); })(); Please enable JavaScript to view the comments powered by Disqus. ```
``` (adsbygoogle = window.adsbygoogle || []).push({}); (adsbygoogle = window.adsbygoogle || []).push({}); ```
``` Recommend Reading How java manages Memory? Why is it advised to use hashcode and equals together? Comparable and Comparator in java How to create Singleton class in Java? Difference betwen equals and ==? When to use abstract class over interface? Difference between final, finally and finalize Why is it recommended to ues Immutable objects in Java Copyright 2018 JavaQuestions, All rights reserved | Sitemap Subscribe to get latest updates. Email Address * ```