[Leedcode][JAVA][第139题][单词拆分][递归][记忆优化][动态规划]

ゝ一纸荒年。 2023-02-20 07:48 7阅读 0赞

#### 【问题描述】\[中等\] ####

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
    
    说明：
    
    拆分时可以重复使用字典中的单词。
    你可以假设字典中没有重复的单词。
    示例 1：
    
    输入: s = "leetcode", wordDict = ["leet", "code"]
    输出: true
    解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
    示例 2：
    
    输入: s = "applepenapple", wordDict = ["apple", "pen"]
    输出: true
    解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
         注意你可以重复使用字典中的单词。
    示例 3：
    
    输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
    输出: false

#### 【解答思路】 ####

###### 1. 动态规划 ######

动态规划流程  
第 1 步：设计状态  
dp\[i\] 表示字符串 ss 前 ii 个字符组成的字符串 s\[0…i-1\]s\[0…i−1\] 是否能被空格拆分成若干个字典中出现的单词

第 2 步：状态转移方程  
![在这里插入图片描述][2020062510294030.png]  
第 3 步：考虑初始化  
boolean\[\] dp = new boolean\[s.length() + 1\];  
第 4 步：考虑输出  
dp\[s.length()\];  
第 5 步：考虑是否可以状态压缩  
**时间复杂度：O(N^2) 空间复杂度：O(n)**  
![在这里插入图片描述][20200625103027322.png]

public class Solution { 
        public boolean wordBreak(String s, List<String> wordDict) { 
            Set<String> wordDictSet = new HashSet(wordDict);
            boolean[] dp = new boolean[s.length() + 1];
            dp[0] = true;
            for (int i = 1; i <= s.length(); i++) { 
                for (int j = 0; j < i; j++) { 
                    if (dp[j] && wordDictSet.contains(s.substring(j, i))) { 
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }
    }

public boolean wordBreak(String s, List<String> wordDict) { 
            if (s == null || s.length() == 0) { 
                return true;
            }
            if (wordDict == null || wordDict.size() == 0) { 
                return false;
            }
            boolean[] dp = new boolean[s.length() + 1];
            dp[0] = true;
            for (int i = 1; i <= s.length(); i++) { 
                for (String word : wordDict) { 
                    int length = word.length();
                    if (i >= length && s.substring(i - length, i).equals(word)) { 
                        dp[i] |= dp[i - length];
                    }
                }
            }
            return dp[s.length()];
        }

###### 2. 暴力递归到记忆优化 ######

**暴力递归(超时)**  
**从头开始遍历s,若遍历到i形成的字符串s\[0-i\]在字典中wordDict，则只要判断s\[i+1 - s.length()\]是否可以被空格拆分为一个或多个在字典中出现的单词即可。以这种思想构建递归**  
**时间复杂度：O(N^2) 空间复杂度：O(N)**

public boolean wordBreak(String s, List<String> wordDict) { 
            // 创建字典中字符串存在的set，创建的同时记录字典中最长的字符串的长度
            HashSet<String> set = new HashSet<>();
            for (String str : wordDict) { 
                set.add(str);
            }
            return getResult(s,0,set);
        }
    
        private boolean getResult(String s, int start, HashSet<String> set) { 
            if(start == s.length()){ 
                return true;
            }
            for (int i = start;i < s.length(); i++) { 
                if(set.contains(s.substring(start,i + 1))){ 
                    if(getResult(s,i+1,set)){ 
                        return true;
                    }
                }
            }
            return false;
        }

**memorization技术优化**  
**考虑到每次计算getResult(s,i+1,set)回带来大量重复的计算，所以这里使用memorization技术存储重复计算的结果**

public boolean wordBreak(String s, List<String> wordDict) { 
            HashSet<String> set = new HashSet<>();
            for (String str : wordDict) { 
                set.add(str);
            }
            HashMap<Integer,Boolean> memo = new HashMap<Integer,Boolean>();
            return getResult(s,0,set,memo);
        }
    
        private boolean getResult(String s, int start, HashSet<String> set,HashMap<Integer,Boolean> memo) { 
            if(start == s.length()){ 
                return true;
            }
            if(memo.containsKey(start)){ 
                return memo.get(start);
            }
            for (int i = start;i < s.length(); i++) { 
                if(set.contains(s.substring(start,i + 1))){ 
                    if(getResult(s,i+1,set,memo)){ 
                        memo.put(start,true);
                        return true;
                    }
                }
            }
            memo.put(start,false);
            return false;
        }

**遍历优化 \*\*  
考虑到每次遍历s字符串，检查是否在set中存在是，每次都是从头遍历到尾，这样必定回带来大量的无效遍历，如果**当前遍历的长度大于字段中字符串的最大长度\*\*，则一定不可能匹配成功。

public boolean wordBreak(String s, List<String> wordDict) { 
            HashSet<String> set = new HashSet<>();
            int max = Integer.MIN_VALUE;
            for (String str : wordDict) { 
                max = Math.max(str.length(),max);
                set.add(str);
            }
            // 记录map，记录重复的计算的结果
            HashMap<Integer,Boolean> map = new HashMap<>();
            return getResult(s,0,set,max,map);
        }
    
        /** * * @param s * @param start 表示索引开始位置 * @param set 字段中字符串的集合 * @param max 每次遍历s时不可以超出max长度，否则肯定为false * @param map 记忆表 * @return */
        private boolean getResult(String s, int start, HashSet<String> set,int max,HashMap<Integer,Boolean> map) { 
            if(start == s.length()){ 
                return true;
            }
            if(map.containsKey(start)){ 
                return map.get(start);
            }
            // 关键步骤： 遍历的时候加上max的长度限制，避免无限遍历至s结尾
            for (int i = start; i < start + max && i < s.length(); i++) { 
                if(set.contains(s.substring(start,i + 1))){ 
                    if(getResult(s,i+1,set,max,map)){ 
                        map.put(start,true);
                        return true;
                    }
                }
            }
            map.put(start,false);
            return false;
        }

#### 【总结】 ####

###### 1.动态规划流程 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

###### 2. 递归 耗时 memorization技术优化 ######

###### 3.一开始只想到递归 没有想到动态规划 ######

参考链接：https://leetcode-cn.com/problems/word-break/solution/javacong-bao-li-di-gui-dao-ji-yi-you-hua-by-ngu-6/  
参考链接：https://leetcode-cn.com/problems/word-break/solution/dan-ci-chai-fen-by-leetcode-solution/  
参考链接：https://leetcode-cn.com/problems/word-break/solution/java-dong-tai-gui-hua-by-kelly2018/

[2020062510294030.png]: https://img-blog.csdnimg.cn/2020062510294030.png
[20200625103027322.png]: https://img-blog.csdnimg.cn/20200625103027322.png