发表于 更新于

动态规划之单词拆分

leetcode.139

先决条件

首先看到这题，我们必须明确，至少是一个二重循环以上的算法。因为必须要同时遍历s字符串和wordDict字符数组。

这题用动态规划显然是一个比较优的解法。我们先设一个dp数组，dp[i]的值代表着s下标从0到i是否能用wordDict中的单词拼接。

状态转移方程

对于动态规划，状态转移方程是非常重要的。以下是这个算法的核心代码。

1
dp[i]=(dp[i-wordDict[j].size()]&&res==wordDict[j]);

我们来慢慢咀嚼。看一下下面这个案例：

1
2
3
wordDict = ["apple", "pen"]
a p p l e p e n a  p  p  l  e
1 2 3 4 5 6 7 8 9 10 11 12 13

对于任意一个dp[i]我们都可以由前面的dp值推出。例如，当i等于8时，dp[8]表示s从1到8这段区间（至于为什么不是从0开始我们后面再说）是否能被拼接。显然是可以的。至于怎么推呢。我们看到，dp[5]（apple）显然也是能被拼接的，那么dp[8]是否为true取决于i=5和i=8之间的字符串（pen），显然pen是wordDict数组里的值，因此dp[8]=dp[5]=true.

我们根据上述规律可以建立转移方程：对于任意一个dp[i]我们都可以根据dp[i-wordDict[j].size()]和res是否等于wordDict[j]这两个条件来判断。

dp[i-wordDict[j].size()]表示下标i减去wordDict数组里的一个单词的长度所得到的dp的值。

res表示上述两个下标之间所夹的字符串。

如果dp[i-wordDict[j].size()]和res==wordDict[j]同时成立，那么我们就认为dp[i]是true，有任意一个条件不满足我们就认为dp[i]是false.

代码解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int i,j;
        string res;
        int n=s.size();
        int m=wordDict.size();
        dp[0]=true;
        s=" "+s;//使得s字符串下标从1开始
        vector<bool>dp(n+1,false);//dp数组类型为bool，全部赋值false
        for(i=1;i<=n;i++){
            for(j=0;j<m;j++){
                if(i>=wordDict[j].size()){
                    res=s.substr(i-wordDict[j].size()+1,wordDict[j].size());//具体看string复制函数————substr
                    if(dp[i]==false)dp[i]=(dp[i-wordDict[j].size()]&&res==wordDict[j]);//core
                }
            }
        }
        return dp[n];//返回结果
    }
};

  • 为什么下标从1开始

    由于dp需要递推，我们需要将初始的dp[0]设置为true才能保证后续的递推。

  • 为什么状态转移方程前面需要加一个特判dp[i]==false

    我们知道，wordDict中的字符串是无序的，因此遍历也是无序的，如果一开始就遍历到了能拼接的单词，使得dp[i]=true，但当遇到了不符合的单词，false则会覆盖掉之前的true，导致结果错误。因此我们只对值为false的dp数组进行操作。