leetcode 139. Word Break 深度优先遍历DFS按照index递归搜索 + 很棒的动态规划DP做法

系统管理员 2022-06-08 06:00 148阅读 0赞

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given  
s = “leetcode”,  
dict = \[“leet”, “code”\].

Return true because “leetcode” can be segmented as “leet code”.

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.

这道题使用DFS很直觉，但是你会发现会出现问题，一些benchmark过不了，主要是类似aaaa、aaa的wordList和aaaaaaa的配对就会出现问题，所以我这里**稍微修改了递归做法**。

使用DP的思路如下：

boolean []dp = new boolean[s.length()+1];
    dp[0] = true;

dp\[i\]表示1到i的字符是可以分割的，那么  
dp\[i\]=true 当且仅当 dp\[j\]=true && wordList包含字符串i到j。  
直接看代码更直接。

这道题[leetcode 472. Concatenated Words 连接字符串的判定 + 动态规划DP实现][leetcode 472. Concatenated Words _ _ _DP] 是本题的一个升级，值得一起学习

代码如下：

import java.util.List;
    
    /*
     * 你也能看出来使用DP和递归去做，但是就是做不出来
     * http://www.cnblogs.com/reboot329/p/6168346.html
     * */
    public class Solution
    {
        
        /*
         * 下面是DFS做法，但是有问题，对于类似{aaaa,aaa}和aaaaaaa的benchmark会出现问题
         *  
         * */
        public boolean wordBreakByDFS(String s, List<String> wordDict)
        {
            return byDFS(s,wordDict,0);
        }
        boolean byDFS(String s, List<String> wordDict, int index) 
        {
            if(index>=s.length())
                return true;
            else 
            {
                for(int i=index+1;i<=s.length();i++)
                {
                    String key=s.substring(index, i);
                    if(wordDict.contains(key))
                    {
                        wordDict.remove(key);
                        boolean res=byDFS(s, wordDict, i);
                        if(res==false)
                            wordDict.add(key);
                    }
                }
                return false;
            }   
        }
    
        /*
         * dp[i]表示1-i的字符串是可以分割的
         * dp[0]代表永远可分
         * */
        public boolean wordBreak(String s, List<String> 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++)
                {
                    //这个条件的意识是0到j可以分割，同时j到i又在wordDic里面，
                    //所以0到i可以分割，一旦确定可以分割就可以break了
                    if(dp[j] && wordDict.contains(s.substring(j, i)))
                    {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }
    }

下面是C++的做法，**当你遇到字符串匹配的时候就该自然而然的想到使用DP动态规划来做**，所以本题就该使用DP动态规划来做

代码如下：

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <string>
    #include <map>
    #include <set>
    #include <climits>
    
    using namespace std;
    
    class Solution 
    {
    public:
        bool wordBreak(string s, vector<string>& wordDict) 
        {
            set<string> st(wordDict.begin(),wordDict.end());
            vector<bool> dp(s.length()+1,false);
            dp[0] = true;
            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;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }
    };

[leetcode 472. Concatenated Words _ _ _DP]: http://blog.csdn.net/JackZhang_123/article/details/78814598