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); } } }