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