DP32 單詞按照字典分割問題 Word Break Problem @geeksforgeeks

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".

Recursive implementation:
The idea is simple, we consider each prefix and search it in dictionary. If the prefix is present in dictionary, we recur for rest of the string (or suffix). If the recursive call for suffix returns true, we return true, otherwise we try next prefix. If we have tried all prefixes and none of them resulted in a solution, we return false.

經典DFS題目，把DFS改成DP能減少運算量

package DP;

import java.util.ArrayList;

public class WordBreak {

	public static void main(String[] args) {
		System.out.println(wordBreakRec("ilikesamsung"));
		System.out.println(wordBreakDP("ilikesamsung"));
		wordBreakPrintAll("ilikesamsung");
		System.out.println(wordBreakRec("samsungandmango"));
		System.out.println(wordBreakDP("samsungandmango"));
		wordBreakPrintAll("samsungandmango");
		System.out.println(wordBreakRec("samsungandmangok"));
		System.out.println(wordBreakDP("samsungandmangok"));
		wordBreakPrintAll("samsungandmangok");
	}
	
	public static boolean wordBreakRec(String s){
		int len = s.length();
		if(len == 0){
			return true;
		}
		
		// DFS
		// Try all prefixes of lengths from 1 to size
		for(int i=1; i<=len; i++){
			// The parameter for dictionaryContains is s.substring(0, i)
	        // s.substring(0, i) which is prefix (of input string) of
	        // length 'i'. We first check whether current prefix is in
	        // dictionary. Then we recursively check for remaining string
	        // s.substring(i) which is suffix of length size-i
			if(dictionaryContains(s.substring(0, i)) && wordBreakRec(s.substring(i))){
				return true;
			}
		}
		
		// If we have tried all prefixes and none of them worked
		return false;
	}
	
	// 打印出所有組合，因為要打印出所有組合而不只是判斷能否，所以只能用dfs
	public static void wordBreakPrintAll(String s){
		ArrayList al = new ArrayList();
		wordBreakRec2(s, al);
	}

	public static void wordBreakRec2(String s, ArrayList al){
		int len = s.length();
		if(len == 0){
			System.out.println(al);
			return;
		}
		
		// DFS
		for(int i=1; i<=len; i++){
			String substr = s.substring(0, i);
			if(dictionaryContains(substr)){
				al.add(substr);
				wordBreakRec2(s.substring(i), al);
				al.remove(al.size()-1);
			}
		}
	}
	
	private static boolean dictionaryContains(String word){
		String[] dict = {"mobile","samsung","sam","sung","man","mango",
                			"icecream","and","go","i","like","ice","cream"};
		for(int i=0; i




http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/