LeetCode笔记：140. Word Break II

秒速五厘米 2022-01-05 13:45 241阅读 0赞

# 题目描述 #

![1655095-20190424170833682-1739409176.png][]

![1655095-20190424170907570-1231294814.png][]

给定一个非空的字符串s，一个非空的字符串list作为字典。通过在s中添加空格可以将s变为由list中的word表示的句子，要求返回所有可能组成的句子。设定list中的word不重复，且每一个word都可以重复使用。

# 算法一 #

先来一个暴力的方法，如下图所示：1）用一个currStr记录当前句子，初始为“”，两个指针start、end分别表示当前词word的起始和结束；2）如果word在list中则将其加入currStr中，start = end +1，否则end后移；3）重复 2）操作直到end超出s的范围。4）可以先计算list中最长word 的长度，作为end后移次数的长度限制。

这种算法存在需要对同一子字符串需要重复计算的情况，提交代码时显示Time Limit Exceeded

![1655095-20190424174109494-221482601.png][]

class Solution {   
        public static int maxLen = 0;
        public List<String> wordBreak(String s, List<String> dict) {
            List<String> res = new ArrayList<String>();
            if(dict.size() == 0 || s == null || s.length() == 0) return res;
            maxLen = getMaxLen(dict);
            dfs(s, dict, 0, res);
            return res;
        }
        
        public void dfs(String s, List<String> dict, int index, List<String> res){
            if(index >= s.length()){
                res.add(s.trim());
                return;
            }
            for(int i=index+1; (i<=index + maxLen) && (i<=s.length()); i++){
                String word = s.substring(index, i);
                if(inDict(word, dict)){
                    String newStr = s.substring(0, i) + " " + s.substring(i, s.length());
                    dfs(newStr, dict, i+1, res);
                }
            }
        }
        
        public boolean inDict(String w, List<String> s){
            for(String str : s){
                if(str.equals(w)){
                    return true;
                }
            }
            return false;
        }
        
        public int getMaxLen(List<String> s){
            int max = 0;
            for(String str:s){
                max = max > str.length()?max : str.length();
            }
            return max;
        }
    }

#  算法二 #

算法一之所以会超时，原因是可能对同一个的子字符串重复计算。例如s = “abcdabccc”,list = \{"ab", "cd", "abcd", "ccc"\}。当currStr = “ab cd”时，要对剩余子字符串“abccc”计算一次，currStr = “abcd”时，还需要对“abccc”再进行一次计算。这就是所谓的子问题重复的情况了，因此可以用动态规划来解决问题。

用一个Map来存储子字符串和其对应的所有句子组合方式。但对某一个字符串s进行查询时：若Map中包含该字符串的组合方式，则直接返回；否则，对每一个位于s开头且包含于list中的word，计算其剩余子串的句子组合方式，将其与该单词组合成新的句子。

class Solution {
        public List<String> wordBreak(String s, List<String> wordDict) {
            if(s == null || wordDict == null) return null;
            return helper(s, wordDict, new HashMap<String, List<String>>());
        }
        
        private List<String> helper(String s, List<String> wordDict, 
                                    HashMap<String, List<String>> dp){
            if(dp.containsKey(s)) return dp.get(s);
            
            List<String> res = new ArrayList<>();
            if(s.length() == 0) {
                res.add("");
                dp.put("", res);
                return res;
            }
            
            for(int i=0; i<wordDict.size(); i++) {
                String word = wordDict.get(i);
                if(s.startsWith(word)) {
                    List<String> restRes = helper(s.substring(word.length(), s.length()), 
                                                 wordDict, dp);
                    if(restRes.size() != 0) {
                        for(String eleInRest : restRes) {
                            if(eleInRest.length() == 0) {
                                res.add(word);
                            }else{
                                res.add(word + " " + eleInRest);
                            }
                        }
                    }
                }
            }
            dp.put(s, res);
            return res;
        }
    }

转载于:https://www.cnblogs.com/NelsonProgram/p/10763840.html

[1655095-20190424170833682-1739409176.png]: /images/20211229/761180d77f774a1297dab71ef84fbda7.png
[1655095-20190424170907570-1231294814.png]: /images/20211229/98a2c3cc17864851b98143d12c429043.png
[1655095-20190424174109494-221482601.png]: /images/20211229/04608ec8b0ed457c8d81cf386e1f6a94.png