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/