【LeetCode】Word Break II 动态规划

本文主要是介绍【LeetCode】Word Break II 动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：Word Break

要求找到所有能够有字典中的词重组成目标串的结果 

 public class Solution {public static List<String> wordBreak(String s, Set<String> dict) {List<String> dp[] = new ArrayList[s.length()+1];dp[0] = new ArrayList<String>();for(int i=0; i<s.length(); i++){//i是开始位置if( dp[i] == null ) continue; //前面的部分必须是可以匹配的for(String word:dict){int len = word.length();int end = i+len;if(end > s.length()) continue;if(s.substring(i,end).equals(word)){if(dp[end] == null){dp[end] = new ArrayList<String>();}dp[end].add(word);//记录上一个位置}}}List<String> ans = new LinkedList<String>();if(dp[s.length()] == null) return ans; ArrayList<String> tmp = new ArrayList<String>();dfsStringList(dp,s.length(),ans, tmp);return ans;}public static void dfsStringList(List<String> dp[],int end,List<String> res, ArrayList<String> tmp){if(end <= 0){String ans = tmp.get(tmp.size()-1);for(int i=tmp.size()-2; i>=0; i--)ans += (" " + tmp.get(i) );res.add(ans);return;}for(String str:dp[end]){tmp.add(str);dfsStringList(dp,end-str.length(), res, tmp);tmp.remove(tmp.size()-1);}}
} 

这篇关于【LeetCode】Word Break II 动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---