leetCode ！！ word break

方法一：字典树+动态规划
首先,创建node类，每个对象应该包含:一个node array nexts(如果有通往’a’的路，那么对应的nexts[0]就不该为null); 一个boolean 变量（如果到达的这个字母恰好是字典中某个候选串的结尾，那么 标记end=true）;
然后，根据 字典，建立字典树；
接着，使用动态规划的方式，检查目标字符串str是否可以用字典中的候选串拼出来。具体地，dp[i]表示 str[i…] 是否可以用字典中的候选串拼出来。对于str[i…]，枚举第一子串该如何划分，str[i…end]中end可取值i,i+1,…。检查str[i…end]是否在字典中，对应地余下str[end+1,…]是否也可以 用字典中的候选串拼出来，即dp[end+1]==true么? 二者都成立说明 str[i…]可以用字典中的候选串拼出来， 即dp[i]==true.对于str[i…]来说，只要找到一种拼接方式即可，于是break,去枚举下一个str[i-1,…]是否可以用字典中的候选串拼出来。

  public boolean wordBreak(String word, List<String> dict){// build a treeNode root = new Node();for(String s:dict){Node cur = root;int index=0;char[] str = s.toCharArray();for(char c:str){index = c-'a';if(cur.nexts[index]==null){cur.nexts[index]=new Node();}cur = cur.nexts[index];}cur.end=true;}// checkchar[] chs = word.toCharArray();// dp[i]int n= chs.length;boolean[] dp = new boolean[n+1];dp[n]=true;// !!// if str[i..n-1] can be done, //then obviously dp[i] = str[i...n-1]&&dp[n] = true; // so dp[n] should be true;for(int i=n-1;i>=0;i--){Node cur = root;for(int end=i;end<n;end++){int index = chs[end]-'a';if(cur.nexts[index]==null) {break;// 剪枝，避免了无效的枚举}cur = cur.nexts[index];if(cur.end&&dp[end+1]){dp[i]=true;break;}}}return dp[0];}

方法2： 递归函数+哈希表
写一个递归函数 str[index…] ，以字典为标本，有多少种分解方式.
注：在力扣上做测试，它超过了时间限制。

public static boolean wordBreak(String s, List<String> wordDict) {return process(s, 0, new HashSet<>(wordDict)) != 0;}// s[0......index-1]这一段，已经分解过了，不用在操心// s[index.....] 这一段字符串，能够被分解的方法数，返回public static int process(String s, int index, HashSet<String> wordDict) {if (index == s.length()) {// this cutting pattern is acceptedreturn 1;}// index没到最后// index...index// index...index+1// index....index+2// index....endint ways = 0;for (int end = index; end < s.length(); end++) {// s[index....end]String pre = s.substring(index, end + 1);if (wordDict.contains(pre)) {ways += process(s, end + 1, wordDict);}}return ways;}

方法三：动态规划+哈希表

在方法一的基础上，把字典树换成哈希表。
运行效率上，显然不如用字典树的方法一。这主要是因为方法一中间遇到不在Trie上的字符就break，进入下一个开头的尝试，这可以视为一种“剪枝”，避免不必要的操作。
而，这里使用哈希表，只要用substring函数切出来的，都检查他是否在哈希表中，所以费时。

public boolean wordBreak(String word,List<String> dict){int n = word.length();char[] str = word.toCharArray();boolean[] dp = new boolean[n+1];dp[n]=true;HashSet<String> set = new HashSet<>(dict);for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(set.contains(word.substring(i, j+1))&&dp[j+1]){dp[i] = true;}}}return dp[0];}