leetcode 140. Word Break II 深度优先搜索DFS + 很棒的动态规划DP 做法 + 记录前驱节点

妖狐艹你老母 2022-06-08 06:05 189阅读 0赞

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given  
s = “catsanddog”,  
dict = \[“cat”, “cats”, “and”, “sand”, “dog”\].

A solution is \[“cats and dog”, “cat sand dog”\].

UPDATE (2017/1/4):  
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

和上一道题一样[leetcode 139. Word Break DP + DFS按照index递归搜索][leetcode 139. Word Break DP _ DFS_index]。

**这道题需要学习的地方是设置前置结点，这个需要好好学习！**

注意记录的是前驱节点，这个index是+1的，所以这点需要注意，别的都还行

不过这第一道题最直觉的方法是DFS，但是会超时，所以还是按照DP+DFS的思路去做。

代码如下：

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    /*
     * 还是使用DP解决， 
     * */
    public class Solution 
    {
         List<String> res = new ArrayList<String>();
    
         /*
          * 下面是DFS做法，会发现超算
          * */
         public List<String> wordBreakByDFS(String s, List<String> wordDict) 
         {
             List<String> one = new ArrayList<>();
             byDFS(s, wordDict, one, 0);
             return res;
         }
         void byDFS(String s, List<String> wordDict,List<String> one, int index) 
         {
                if(index>=s.length())
                {
                    String tmp="";
                    for(int i=0;i<one.size()-1;i++)
                        tmp=tmp+one.get(i)+" ";
                    tmp+=one.get(one.size()-1);
                    res.add(tmp);
                }
                else 
                {
                    for(int i=index+1;i<=s.length();i++)
                    {
                        String key=s.substring(index, i);
                        if(wordDict.contains(key))
                        {
                            one.add(key);
                            byDFS(s, wordDict,one, i);
                            one.remove(one.size()-1);
                        }
                    }
                }   
         }
    
    
        /*
         * 这个是DP解决方法
         * */
        public List<String> wordBreak(String s, List<String> wordDict) 
        {
            boolean []flag = new boolean[s.length()+1];
            flag[0]=true;
    
            List<List<Integer>> preIndex = new ArrayList<>();
            for(int i=0;i<s.length()+1;i++)
                preIndex.add( new ArrayList<>() );
            preIndex.get(0).add(0);
    
            for(int i=1;i<s.length()+1;i++)
            {
                for(int j=0;j<i;j++)
                {
                    if(flag[j] && wordDict.contains(s.substring(j, i)))
                    {
                        flag[i] = true;
                        preIndex.get(i).add(j);
                    }
                }
            }
    
            if(flag[s.length()])
            {
                List<String> one = new ArrayList<>();
                DFS(preIndex,one,s,wordDict,s.length());
            }
            return res;
        }
    
        void DFS(List<List<Integer>> preIndex, List<String> one,String s, List<String> wordDict, int length) 
        {
            if(length == 0)
            {
                String str = "";
                for(int i=one.size()-1;i>=1;i--)
                    str = str + one.get(i)+" ";
                str = str + one.get(0);
                res.add(str);
            }else
            {
                List<Integer> index = preIndex.get(length);
                for(int i=0;i<index.size();i++)
                {
                    one.add(s.substring(index.get(i),length));
                    DFS(preIndex, one, s, wordDict, index.get(i));
                    one.remove(one.size()-1);
                }
            }
        }
    }

下面是C++的做法，就是先使用DP做分割，然后使用DFS深度优先遍历来获取所有的可能的分割结果

和之前的一样，做DP的过程中还是使用前置链表来纪录相关关系

代码如下：

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <string>
    #include <map>
    #include <set>
    #include <climits>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<string> res;
        vector<string> wordBreak(string s, vector<string>& wordDict)
        {
            set<string> st(wordDict.begin(),wordDict.end());
            vector<bool> dp(s.length()+1,false);
            dp[0] = true;
            vector<vector<int>> preIndex(s.length()+1,vector<int>());
            preIndex[0].push_back(0);
            for (int i = 1; i <= s.length(); i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if ( dp[j] && st.find(s.substr(j, (i - 1)-j+1)) != st.end())
                    {
                        dp[i] = true;
                        preIndex[i].push_back(j);
                    }
                }
            }
            if (dp[s.length()])
            {
    
                getAll(s, preIndex, vector<string>(), s.length());
            }
            return res;
        }
    
        void getAll(string s, vector<vector<int>> preIndex,vector<string> one,int index)
        {
            if (index == 0)
            {
                string a = "";
                for (int i = one.size() - 1; i >= 1; i--)
                    a += one[i] + " ";
                a += one[0];
                res.push_back(a);
                return;
            }
            else
            {
                for (int pre : preIndex[index])
                {
                    one.push_back(s.substr(pre,(index-1)-pre+1));
                    getAll(s,preIndex,one,pre);
                    one.erase(one.end()-1);
                }
            }
        }
    };

[leetcode 139. Word Break DP _ DFS_index]: http://blog.csdn.net/jackzhang_123/article/details/78009135