潍坊网站建设中公,有网站建设的虚拟主机管理系统,建站软件免费模板,wordpress 网页计算器方法一#xff1a;字典树动态规划 首先,创建node类#xff0c;每个对象应该包含:一个node array nexts(如果有通往’a’的路#xff0c;那么对应的nexts[0]就不该为null); 一个boolean 变量#xff08;如果到达的这个字母恰好是字典中某个候选串的结尾#xff0c;那么 标记…方法一字典树动态规划 首先,创建node类每个对象应该包含:一个node array nexts(如果有通往’a’的路那么对应的nexts[0]就不该为null); 一个boolean 变量如果到达的这个字母恰好是字典中某个候选串的结尾那么 标记endtrue; 然后根据 字典建立字典树 接着使用动态规划的方式检查目标字符串str是否可以用字典中的候选串拼出来。具体地dp[i]表示 str[i…] 是否可以用字典中的候选串拼出来。对于str[i…]枚举第一子串该如何划分str[i…end]中end可取值i,i1,…。检查str[i…end]是否在字典中对应地余下str[end1,…]是否也可以 用字典中的候选串拼出来即dp[end1]true么? 二者都成立说明 str[i…]可以用字典中的候选串拼出来 即dp[i]true.对于str[i…]来说只要找到一种拼接方式即可于是break,去枚举下一个str[i-1,…]是否可以用字典中的候选串拼出来。 public boolean wordBreak(String word, ListString dict){// build a treeNode root new Node();for(String s:dict){Node cur root;int index0;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.endtrue;}// checkchar[] chs word.toCharArray();// dp[i]int n chs.length;boolean[] dp new boolean[n1];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 in-1;i0;i--){Node cur root;for(int endi;endn;end){int index chs[end]-a;if(cur.nexts[index]null) {break;// 剪枝避免了无效的枚举}cur cur.nexts[index];if(cur.enddp[end1]){dp[i]true;break;}}}return dp[0];}方法2 递归函数哈希表 写一个递归函数 str[index…] 以字典为标本有多少种分解方式. 注在力扣上做测试它超过了时间限制。
public static boolean wordBreak(String s, ListString wordDict) {return process(s, 0, new HashSet(wordDict)) ! 0;}// s[0......index-1]这一段已经分解过了不用在操心// s[index.....] 这一段字符串能够被分解的方法数返回public static int process(String s, int index, HashSetString wordDict) {if (index s.length()) {// this cutting pattern is acceptedreturn 1;}// index没到最后// index...index// index...index1// index....index2// 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,ListString dict){int n word.length();char[] str word.toCharArray();boolean[] dp new boolean[n1];dp[n]true;HashSetString set new HashSet(dict);for(int in-1;i0;i--){for(int ji;jn;j){if(set.contains(word.substring(i, j1))dp[j1]){dp[i] true;}}}return dp[0];}
