Word Break Problem Java Solution

Word Break Problem Java Solution

Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details.
This is a famous Google interview question, also being asked by many other companies now a days.

Consider the following dictionary 

{ i, like, sam, sung, samsung, mobile, ice, 
  cream, icecream, man, go, mango}

Input:  ilike
Output: Yes
The string can be segmented as "i like".

Input:  ilikesamsung
Output: Yes

The string can be segmented as "i like samsung" or
"i like sam sung".

i have given two solution in my sample code.you can use any of them.i have given solution is
using HashSet and other one using simple logic.

Sample Code:

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class WordBreakProblemApp
{
private static Set<String> DICTIONARY = new HashSet<String>();
static
{
DICTIONARY.add("mobile");
DICTIONARY.add("samsung");
DICTIONARY.add("sam");
DICTIONARY.add("sung");
DICTIONARY.add("man");
DICTIONARY.add("mango");
DICTIONARY.add("icecream");
DICTIONARY.add("and");
DICTIONARY.add("go");
DICTIONARY.add("i");
DICTIONARY.add("love");
DICTIONARY.add("ice");
DICTIONARY.add("cream");
}

private static boolean existInDictionary(String string)
{
return DICTIONARY.contains(string.toLowerCase());
}

private static void wordutil(String input)
{
processInputString(input, input.length(), "");
}

private static void processInputString(String input, int size, String result)
{

for (int i = 1; i <= size; i++)
{
if (existInDictionary(input.substring(0, i)))
{
if (i == size)
{
  System.out.println(result + " " + input);
  break;
}

else
{
  processInputString(input.substring(i, size), size - i,
  result + " " + input.substring(0, i) + " ");
}
}
 }
}

public static void main(String[] args)
{
   wordutil("ilovesamsungmobile");
}


/*********You can use this method too.it is optional****************/

   public boolean wb(int start, String str, List<String> wordDict, StringBuilder sb)
   {
        for(int i=start; i<str.length(); i++)
        {
                String sub = str.substring(start,i+1);
                System.out.println(sub);
                if(wordDict.contains(sub))
                {
                    sb.append(sub);
                    if(sb.length() == str.length())
                    {
                        return true;
                    }
                 
                    boolean r = wb(i+1, str, wordDict, sb);
                    if(r) return r;
                    sb.setLength(sb.length()-sub.length());
                }
        }
        return false;
    }
}

Output:

 i  love  sam  sung  mobile
 i  love  samsung  mobile