LeetCode 140. 单词拆分 II JAVA

﹏ヽ暗。殇╰゛Y 2022-11-21 11:45 163阅读 0赞

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

分隔时可以重复使用字典中的单词。  
你可以假设字典中没有重复的单词。

示例 1：
    
    输入:
    s = "catsanddog"
    wordDict = ["cat", "cats", "and", "sand", "dog"]
    输出:
    [
      "cats and dog",
      "cat sand dog"
    ]
    示例 2：
    
    输入:
    s = "pineapplepenapple"
    wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
    输出:
    [
      "pine apple pen apple",
      "pineapple pen apple",
      "pine applepen apple"
    ]
    解释: 注意你可以重复使用字典中的单词。
    示例 3：
    
    输入:
    s = "catsandog"
    wordDict = ["cats", "dog", "sand", "and", "cat"]
    输出:
    []
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/word-break-ii
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：要注意先利用单词拆分I的方法判断是否能够拆分，这样才不会超时。  
单词拆分I :https://blog.csdn.net/weixin\_43981315/article/details/109426338  
使用哈希表存储字符串 s 的每个下标和从该下标开始的部分可以组成的句子列表，在回溯过程中如果遇到已经访问过的下标，则可以直接从哈希表得到结果，而不需要重复计算。如果到某个下标发现无法匹配，则哈希表中该下标对应的是空列表

class Solution {
        
        List<String> res;
         public boolean wordBreak2(String s, List<String> wordDict) {
        
            int len=s.length();
            boolean dp[]=new boolean[len+1];
            dp[0]=true;
            for(int i=0;i<len;i++){
        
                for(int j=0;j<=i;j++){
        
                    if(dp[j]==true&&wordDict.contains(s.substring(j,i+1)))
                        dp[i+1]=true;
                }
            }
            return dp[len];
        }
    	    public List<String> wordBreak(String s, List<String> wordDict) {
        
                res=new ArrayList<>();
                 if(wordBreak2(s,wordDict)==false) return res;
    	        Map<Integer,List<Integer>> map=new HashMap<>();
    	        for(int i=0;i<s.length();i++){
        
    	            for(int j=i+1;j<=s.length();j++){
        //记录每一个i可以到达j的字符串
    	                String tmp=s.substring(i,j);
    	                if(wordDict.contains(tmp)){
        
    	                    List<Integer> list=map.getOrDefault(i,new ArrayList<Integer>());
    	                    list.add(j-1);
    	                    map.put(i,list);
    	                }
    	            }
    	        }
    	        dfs(map,0,new StringBuffer(),s.length(),s);
    	        return res;
    	    }
    	    public void dfs(Map<Integer,List<Integer>>map,int index,StringBuffer buffer,int end,String s){
        //回溯得到所有可能的拆分情况
    	        if(index==end) res.add(buffer.toString());
    	        if(index!=0) buffer.append(" ");/*增加空格*/
    	        List<Integer> next=map.getOrDefault(index,new ArrayList<Integer>());
    	        for(int i=0;i<next.size();i++){
        
    	            String tmp=s.substring(index,next.get(i)+1);
    	            buffer.append(tmp);
    	            dfs(map,next.get(i)+1,buffer,end,s);
    	            buffer.delete(buffer.length()-tmp.length()-1/*注意减掉空格*/,buffer.length());
    	        }
    	    }
    }