首页 > 其他 > 详细

11yue

时间:2020-11-01 23:03:09      阅读:51      评论:0      收藏:0      [点我收藏+]
展开代码
// 官方
// https://leetcode-cn.com/problems/word-break-ii/solution/dan-ci-chai-fen-ii-by-leetcode-solution/
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Map<Integer, List<List<String>>> map = new HashMap<Integer, List<List<String>>>();
        List<List<String>> wordBreaks = backtrack(s, s.length(), new HashSet<String>(wordDict), 0, map);
        List<String> breakList = new LinkedList<String>();
        for (List<String> wordBreak : wordBreaks) {
            breakList.add(String.join(" ", wordBreak));
        }
        return breakList;
    }

    public List<List<String>> backtrack(String s, int length, Set<String> wordSet, int index, Map<Integer, List<List<String>>> map) {
        if (!map.containsKey(index)) {
            List<List<String>> wordBreaks = new LinkedList<List<String>>();
            if (index == length) {
                wordBreaks.add(new LinkedList<String>());
            }
            for (int i = index + 1; i <= length; i++) {
                String word = s.substring(index, i);
                if (wordSet.contains(word)) {
                    List<List<String>> nextWordBreaks = backtrack(s, length, wordSet, i, map);
                    for (List<String> nextWordBreak : nextWordBreaks) {
                        LinkedList<String> wordBreak = new LinkedList<String>(nextWordBreak);
                        wordBreak.offerFirst(word);
                        wordBreaks.add(wordBreak);
                    }
                }
            }
            map.put(index, wordBreaks);
        }
        return map.get(index);
    }
}
// 超时
class Solution {
    Map<Integer, List<String>> map = new HashMap<>();
    Set<String> set = new HashSet<>();
    int maxL = 0;

    public List<String> wordBreak(String s, List<String> wordDict) {
        for(String word: wordDict){
            set.add(word);
            maxL = Math.max(maxL, word.length());
        }

        for(int i = s.length()-1; i>=0; i--){
            core(s, i);
        }
        return map.getOrDefault(0, new ArrayList<>());
    }

    private void core(String s, int cur){
        String tar = s.substring(cur, s.length());
        List<String> saveList = new ArrayList<>();
        if(set.contains(tar)){
            saveList.add(tar);
        }
        for(int i = cur+1; i<s.length() && i<=cur+maxL; i++){
            if(!map.containsKey(i))
                continue;
            tar = s.substring(cur, i);
            if(!set.contains(tar))
                continue;
            List<String> ListI = map.get(i);
            for(String endStr : ListI){
                saveList.add(tar + " " + endStr);
            }
        }
        if(cur+maxL<s.length())
            map.remove(cur+maxL);
        if(saveList.size()!=0)
            map.put(cur, saveList);
    }
}

11yue

原文:https://www.cnblogs.com/BWSHOOTER/p/13912228.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!