word break II--LeetCode

今天药忘吃喽~ 2022-08-07 12:55 50阅读 0赞

public ArrayList<String> wordBreak(String s, Set<String> dict) {  
            ArrayList<String> res = new ArrayList<String>();  
            if(s==null || s.length()==0)  
                return res;  
            helper(s,dict,0,"",res);  
            return res;  
        }  
        private void helper(String s, Set<String> dict, int start, String item, ArrayList<String> res)  
        {  
            if(start>=s.length())  
            {  
                res.add(item);  
                return;  
            }  
            StringBuilder str = new StringBuilder();  
            for(int i=start;i<s.length();i++)  
            {  
                str.append(s.charAt(i));  
                if(dict.contains(str.toString()))  
                {  
                    String newItem = item.length()>0?(item+" "+str.toString()):str.toString();  
                    helper(s,dict,i+1,newItem,res);  
                }  
            }  
        }

接下来我们列出动态规划的解法，递推式跟[Word Break][]是一样的，只是现在不只要保存true或者false，还需要保存true的时候所有合法的组合，以便在未来需要的时候可以得到。不过为了实现这点，代码量就增大很多，需要一个数据结构来进行存储，同时空间复杂度变得非常高，因为所有中间组合都要一直保存。时间上还是有提高的，就是当我们需要前面到某一个元素前的所有合法组合时，我们不需要重新计算了。不过最终复杂度还是主要取决于结果的数量。代码如下

lass Interval {  
        int start;  
        int end;  
        public Interval(int start, int end) {  
            this.start = start; this.end = end;  
        }  
        public Interval(Interval i) {  
            start = i.start;  
            end = i.end;  
     }  
    }  
    ArrayList<ArrayList<Interval>> deepCopy(ArrayList<ArrayList<Interval>> paths) {  
        if (paths==null) return null;  
        ArrayList<ArrayList<Interval>> res = new ArrayList<ArrayList<Interval>>(paths.size());  
        for (int i=0; i<paths.size(); i++) {  
         ArrayList<Interval> path = paths.get(i);  
         ArrayList<Interval> copy = new ArrayList<Interval>(path.size());  
            for (int j=0; j<path.size(); j++) {  
             copy.add(new Interval(path.get(j)));  
         }  
         res.add(copy);  
        }  
        return res;  
    }  
    public ArrayList<String> wordBreak(String s, Set<String> dict) {  
        ArrayList<String> res = new ArrayList<String>();  
        if (s==null || s.length()==0) return res;  
        Map<Integer, ArrayList<ArrayList<Interval>>> dp = new HashMap<Integer, ArrayList<ArrayList<Interval>>>();  
        dp.put(0, new ArrayList<ArrayList<Interval>>());  
        dp.get(0).add(new ArrayList<Interval>());  
        for (int i=1; i<=s.length(); i++) {  
            for (int j=0; j<i; j++) {  
                String cur = s.substring(j, i);  
                ArrayList<ArrayList<Interval>> paths = null;  
                if (dp.containsKey(j) && dict.contains(cur)) {  
                    paths = deepCopy(dp.get(j));  
                    Interval interval = new Interval(j, i);  
                    for (ArrayList<Interval> path:paths) {  
                        path.add(interval);  
                    }  
                }  
                if (paths != null) {  
                    if (!dp.containsKey(i)) {  
                        dp.put(i, paths);  
                    }   
                    else {  
                  dp.get(i).addAll(paths);  
                 }  
                }  
            }  
        }  
        if (!dp.containsKey(s.length())) {  
            return res;  
        }  
        ArrayList<ArrayList<Interval>> paths = dp.get(s.length());  
        for (int j=0; j<paths.size(); j++) {  
            ArrayList<Interval> path = paths.get(j);  
            StringBuilder str = new StringBuilder();  
            for (int i=0; i<path.size(); i++) {  
                if (i!=0) {str.append(" ");}  
                int start = path.get(i).start;  
                int end = path.get(i).end;  
                str.append(s.substring(start, end));  
            }  
            res.add(str.toString());  
        }  
        return res;  
    }

ps:其实，这个题目和上面http://blog.csdn.net/yusiguyuan/article/details/44996133这个题目很相似，回文的分割和字典树的查找，都是相似的，都是使用递归，然后回溯

来源自网络：http://blog.csdn.net/linhuanmars/article/details/22452163

[Word Break]: http://blog.csdn.net/linhuanmars/article/details/22358863