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”].
这道题是上一道的变形,思路是上一题的DFS解法稍作改动,但是为了通过leetcode中的一个比较tricky的test case,要先用DP的思路判断是否有解。
public class Solution { ArrayList<String> wordBreak(String s, Set<String> dict) { int length = s.length(); //create the word ending character's index list for each character ArrayList<ArrayList<Integer>> record = new ArrayList<ArrayList<Integer>>(length); for(int i = 0;i<length;i++) record.add(new ArrayList<Integer>()); //each character can be the ending character of some word for(int end=length;end>=0;end--){ if(end < length && record.get(end).isEmpty()) continue; //find the starting character for the current ending character for(int runner = end-1;runner >= 0;runner--){ if(dict.contains(s.substring(runner,end))) record.get(runner).add(end); //add current end to start character's list } } ArrayList<String> solutionSet = new ArrayList<String>(); buildSolution(record,0,s,"",solutionSet); return solutionSet; } void buildSolution(ArrayList<ArrayList<Integer>> record, int current, String s, String solution, ArrayList<String> solutionSet){ //iterate on current character's word ending list for(Integer end : record.get(current)){ String sub=s.substring(current,end); /* since the loop may have many iterations, we should keep the reference of "solution", rather than writing as "solution += ..." */ String newSolution = solution+(current==0 ? sub : " "+sub); if(end == s.length()) solutionSet.add(newSolution); else buildSolution(record,end,s,newSolution,solutionSet); } } }
Advertisements