Word Break

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Example

Given s = "lintcode", dict = ["lint", "code"].

Return true because "lintcode" can be break as "lint code".

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

//dp: assuming p[i] means at range of 0-i of string is breakable to words in dictionary //p[i]=true when //1. 0 to i is in dict as one wordBreak //2. p[k]=true and k-i is in dict. where 0<=k<=in //else [p[i]=false String s2 = " "+s;//add a dummy character so that easier to come up a formula int len = s2.length(); boolean p[] = new boolean[len]; p[0]=true; //there are at least two loops, outer loop is for j, inner loop is for k<j for(int j=1;j<len;j++){ //notice j is from 1 so that we can do k+1 for(int k=0;k<j;k++){ p[j] = (p[k] && dict.contains(s2.substring(k+1,j+1))); //in java, substring is begin index and end index, with end exclusive if(p[j])break;//end loop for j if j has been determined to be true } } return p[len-1]; }

The below algorithm is better.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

private static int getMaxDictWordLength(Set<String> dict) { int maxLength = 0; for (String word : dict) { maxLength = Math.max(maxLength, word.length()); } return maxLength; } public static boolean wordBreak(String s, Set<String> dict) { if (s == null || s.length() == 0) { return true; } int maxLength = getMaxDictWordLength(dict); boolean[] p = new boolean[s.length() + 1]; p[0] = true;//assuming pre string is in dict. help to build up formula for (int i = 1; i <= s.length(); i++) { p[i] = false; for (int k = 0; k <= maxLength && k <= i; k++) { if (!p[i - k]) {//this is from 0 to k continue; } String word = s.substring(i - k, i); if (dict.contains(word)) { p[i] = true; break; } } } return p[s.length()]; }