用了两个办法：

（1）试着写了个前缀树，352 ms。

其中最大的trick是要用一个数组 boolean[] searchFlag来记录从s[i]开始的子串(s[i...n-1])是否被搜索过（s[i...n-1]能否由dict的单词组成)。如果被搜索过那就不用再搜索了（因为搜索失败了，如果成功的话程序早已结束）。

import java.util.*;

public class Solution {

	class TrieNode {
		char ch;
		ArrayList
  
    children = new ArrayList
   
    (); TrieNode(char c) { ch = c; } TrieNode() { ch = '\0'; } } public void insert(String word, int ind, TrieNode node) { if (ind == word.length()) { TrieNode nNode = new TrieNode('\0'); node.children.add(nNode); return; } int i; for (i = 0; i < node.children.size(); i++) { if (node.children.get(i).ch == word.charAt(ind)) { insert(word, ind + 1, node.children.get(i)); break; } } if (i == node.children.size()) { TrieNode nNode = new TrieNode(word.charAt(ind)); node.children.add(nNode); insert(word, ind + 1, nNode); } } public boolean search(String s, int ind, TrieNode root, TrieNode node, boolean[] searchFlag) { if (ind == s.length()) { for (int i = 0; i < node.children.size(); i++) if (node.children.get(i).ch == '\0') return true; return false; } if(node == root && searchFlag[ind] == true)//the sub string[i...n-1] has been searched before return false; int i; boolean flag = false; for (i = 0; i < node.children.size(); i++) { if (node.children.get(i).ch == '\0') { // end of word, try to search a new word again flag = search(s, ind, root, root, searchFlag); searchFlag[ind] =true; } else if (node.children.get(i).ch == s.charAt(ind)) { // go on iterate the word flag = search(s, ind + 1, root, node.children.get(i), searchFlag); } if (flag == true) return true; } return false; } public boolean wordBreak(String s, Set
    
      dict) { TrieNode root = new TrieNode(); for (String word : dict) { insert(word, 0, root); } boolean[] searchFlag = new boolean[s.length()]; for(int i=0;i
     
       dict = new HashSet
      
       (Arrays.asList("a","abc","b","cd")); System.out.println(sol.wordBreak(s, dict)); } }
      
     
    
   
  

（2）不用前缀树，直接在set里面查找，因为数据量少的缘故变得更加快了。336ms

public class Solution {

	public boolean search(String s, int beg, Set
  
    dict, boolean[] searchFlag)
	{
		if(beg == s.length())
			return true;
		
		if(searchFlag[beg] == true)
			return false;
		
		boolean flag = false;
		for(int e = beg;e<=s.length();e++)
		{
			String subStr = s.substring(beg,e);
			if(dict.contains(subStr))
			{
				flag = search(s,e,dict,searchFlag);
				if(flag == true)
					return true;
				
				searchFlag[e] = true;
			}
		}
		
		return false;
	}

	public boolean wordBreak(String s, Set
   
     dict) { boolean[] searchFlag = new boolean[s.length()+1]; for(int i=0;i