好贷网好贷款

LeetCode Word Break II 解题报告

发布时间:2016-12-5 22:27:40 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"LeetCode Word Break II 解题报告",主要涉及到LeetCode Word Break II 解题报告方面的内容,对于LeetCode Word Break II 解题报告感兴趣的同学可以参考一下。

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"]. A solution is ["cats and dog", "cat sand dog"]. http://oj.leetcode.com/problems/word-break-ii/ 题意说明:把输入句子按照字典中的单词进行分词,输出所有可能的结果。 动态规划加DFS,很有挑战的一道题。 首先用动态规划,Word Break 1的方法计算出state数组,其中state[i]表示string[i-1]是可被词典中的单词划分的。 具体划分方法是: state[i] = 1 意味着存在j,state[j]==1&&string[j,i]存在与字典中。 计算state数组的时候,用一个hashmap保存生成的string[j,i]。key是i,value是所有可能的j,string[j,i]就是字典中的单词。 这样我们对于一个state[i]为1的单词,从后往前,我们就可以找到所有构成它的组合。 例如:,以catsanddog为例: state[10]  = 1 hash[10] =  7 state[7]  = 1 hash[7] = {4,5} 根据这个表dfs就可以目标字符串了。 AC代码: public class Solution { //state[i]为1,表示:s[0,i]可被字典中的单词划分。 int [] state; //记录以key位置结尾的字典中单词的开始位置 HashMap<Integer, ArrayList<Integer>> wordsMap = new HashMap<Integer, ArrayList<Integer>>(); //用dp生成state表 public void dp(String s, Set<String> dict) { int i = 0; for(i=1;i<=s.length();i++) { for(int j=0;j<i;j++) { if(state[j]==1&&dict.contains(s.substring(j,i))) { state[i] = 1; ArrayList<Integer> array = wordsMap.get(i); if(array==null) { array = new ArrayList<Integer>(); array.add(j); wordsMap.put(i, array); } else { array.add(j); } } } } } public ArrayList<String> wordBreak(String s, Set<String> dict) { ArrayList<String> ret = new ArrayList<String>(); if (s==null || s.length()==0 ||dict.size()==0 ) { return ret; } state = new int [s.length() + 1]; state[0] = 1; String cur = new String(); dp(s,dict); if(state[s.length()]!=1) { return ret; } dfs(s, s.length(), cur, ret, dict); return ret; } //dfs生成所有可能的组合 public void dfs(String s, int start, String cur, ArrayList<String> ret, Set<String> dict) { if(start==0) { ret.add(new String(cur)); return; } //获取所有以start结尾的单词的开始位置 ArrayList<Integer> array = wordsMap.get(start); for(int i=0;i<array.size();i++) { String tt = new String(cur); if(tt.length()!=0) { tt = new String(" ") + tt; } //把这个单词加到cur中 tt = s.substring(array.get(i),start) + tt; dfs(s, array.get(i),tt,ret,dict); } } }

上一篇:Python Tkinter简易计算器
下一篇:Linux常用命令大全

相关文章

相关评论