给定一个字符串 String s = "leetcode"

dict = ["leet", "code"].

查看一下是够是字典中的词语组成。假设是返回true，否则返回false。

下边提供3种思路

1.动态算法

import java.util.HashSet;import java.util.Set;public class WordBreak1 {	public static void main(String[] args) {		//"["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]		//String s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";		String s ="LeetCodea";		Set
     
       dict = new HashSet
      
       ();		dict.add("Leet");		dict.add("Code");		dict.add("a");		System.out.println(wordBreak(s,dict));	}	public static boolean wordBreak(String s, Set
       
         dict) {		boolean[] t = new boolean[s.length() + 1];		t[0] = true; // set first to be true, why?		// Because we need initial state		for (int i = 0; i < s.length(); i++) {			// should continue from match position			if (!t[i])				continue;			for (String a : dict) {				int len = a.length();				int end = i + len;				if (end > s.length())					continue;				if (t[end])					continue;				if (s.substring(i, end).equals(a)) {					t[end] = true;				}			}		}		return t[s.length()];	}}
       
      
     

2.普通算法(1)

import java.util.Set;public class WorkBreak2 {	public boolean wordBreak(String s, Set
     
       dict) {		return wordBreakHelper(s, dict, 0);	}	public boolean wordBreakHelper(String s, Set
      
        dict, int start) {		if (start == s.length())			return true;		for (String a : dict) {			int len = a.length();			int end = start + len;			// end index should be <= string length			if (end > s.length())				continue;			if (s.substring(start, start + len).equals(a))				if (wordBreakHelper(s, dict, start + len))					return true;		}		return false;	}}
      
     

3.普通算法(2)

import java.util.Set;public class WordBreak3 {	public static boolean wordBreak(String s, Set
     
       dict) {		// input validation		// Base case		if (dict.contains(s))			return true;		else {			for (int i = 0; i < s.length(); i++) {				String sstr = s.substring(0, i);				if (dict.contains(sstr))					return wordBreak(s.substring(i), dict);			}		}		return false;	}}
     

可是以上的算法有一个问题，就是遇到这样的情况。INPUT: "programcreek", ["programcree","program","creek"]. 无能为力。

大家讨论下吧？