leetcode-word-break-ii

题目大意

　　https://leetcode.com/problems/word-break-ii/

　　接续之前一篇博客，这道题需要输出解的全部可能。

题目分析

　　直接用DFS会超时，所以加了记忆化搜索就可以了，我用的是map存储，key为s中的下标，value是所有的String组合的list，map.get(i)的含义是s以i为开始的那个子串的解，要注意一下末尾的处理。

代码

public class Solution {
    
    private String str;
    private List<String> words;
    private int len;
    private int[] path;
    private Map<Integer, List<String>> map;
    
    // 大于等于ch的最小index
    private int startSearch(char ch) {
        int left = -1;
        int right = len - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (words.get(mid).charAt(0) >= ch) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
     
    // 小于等于ch的最大index
    private int endSearch(char ch) {
        int left = 0;
        int right = len;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (words.get(mid).charAt(0) <= ch) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    private List<String> search(int idx) {
        List<String> ans = new ArrayList<String>();
        if (idx > str.length() - 1) {
            ans.add(""); // 末尾
            return ans;
        }
        if (map.containsKey(idx)) {
            return map.get(idx);
        }
        String t = str.substring(idx);
        int start = startSearch(str.charAt(idx));
        int end = endSearch(str.charAt(idx));
        if (start > end || start < 0 || start >= len || end < 0 || end >= len) {
            return ans;
        }
        for (int i = start; i <= end; i++) {
            if (t.startsWith(words.get(i))) {
                List<String> tmp = search(idx + words.get(i).length());
                for (String s : tmp) {
                    if (s.equals("")) { //这里注意一下如果是空串，就意味着是末尾了，不要有多余的空格
                        ans.add(words.get(i));
                    } else {
                        ans.add(words.get(i) + " " + s);
                    }
                }
            }
        }
        map.put(idx, ans);
        return ans;
    }
    
    public List<String> wordBreak(String s, List<String> wordDict) {
        len = wordDict.size();
        str = s;
        Collections.sort(wordDict);
        words = wordDict;
        map = new HashMap<Integer, List<String>>();
        return search(0);
    }
}