万字长文！动态规划的终极难题：字符匹配类
- 2019 年 12 月 2 日
- 笔记
这些问题大多在 LeetCode 上面标的都是 hard 难度，弄清楚了这些套路后，回过头去看看推导过程，然后再看看二、三十行的代码量，不知道是否能给你一些新的感悟和认识？
本文全长 1w 字，内容有点干，建议先收藏再阅读！
概论
前面我们说了 矩阵类动态规划 和 序列类动态规划 这两类动规题型，不知道你是否对动态规划有了更多的认识。
这里说一下，将动态规划分不同的题型来讨论主要为了更好地明确思路，往往不同类型的题目有着不同的切题点，当然你熟练了，题目做的多了，对动规思想理解透彻了，拿到一道题目马上能想到状态定义以及递推方程，那其实分不分题型没有任何差别，但是如果没有太多基础的，还是不太建议盲目做题，分题型来学习并总结效果可能会更好。
字符匹配类动态规划，你一听名字就知道和字符串匹配相关，这类题型它其实是 序列类动态规划 的一个递进，它有时也被称为 双序列类动态规划。
在 序列类动态规划 中，题目的输入是一个数组或是字符串，然后让你基于这个输入数组或是字符串进行一系列的判断，往往我们拆解问题、分析状态的时候只需要考虑一个维度的状态，比如刷房子和抢房子相关的问题，我们只需要考虑此时的房子和之前考虑过的房子之间的联系，思维始终是在一条线上。
回到字符匹配类动态规划，题目要你分析的是两个序列彼此之间的联系，这里其实有一个动态规划状态维度的提升，在考虑当前子问题的时候，我们要同时考虑两个序列的状态，当然，一般说来，动态规划状态维度的提升，也意味着难度的提升，可能刚从一维变成二维，你会不太习惯，没关系，多思考就好了，对于字符匹配类动态规划，它的题目特征其实特别明显，比如：
- 输入是两个字符串，问是否通过一定的规则相匹配
- 输入是两个字符串，问两个字符串是否存在包含被包含的关系
- 输入是两个字符串，问一个字符串怎样通过一定规则转换成另一个字符串
- 输入是两个字符串，问它们的共有部分
- 。。。
另外说一下，这类问题的难点在于问题的拆解上面，也就是如何找到当前问题和子问题的联系。
往往这类问题的状态比较好找，你可以先假设状态 dp[i][j] 就是子问题 str1(0...i) str2(0...j) 的状态。拆解问题主要思考 dp[i][j] 和子问题的状态 dp[i - 1][j]，dp[i - 1][j] 以及 dp[i - 1][j - 1] 的联系，因为字符串会存在空串的情况，所以动态规划状态数组往往会多开一格。
当然，对于这类问题，如果你还是没有什么思路或者想法，我给你的建议是 画表格，我们结合实际题目一起来看看。
题目分析
LeetCode 第 1143 号问题：最长公共子序列。
题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace"，它的长度为 3。
示例 2:
输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc"，它的长度为 3。
示例 3:
输入：text1 = "abc", text2 = "def" 输出：0 解释：两个字符串没有公共子序列，返回 0。
题目分析
让你求两个字符串的最长公共子序列，这道题目可谓是教科书般的经典，很多算法书籍都把这道题当作动态规划的思维范例进行讲解。
比如大名鼎鼎的 算法导论 ！！！
因此没做过的话，还是强烈建议去做一下。
这里还是按之前的四个步骤来思考，当然这只是一个框架用来辅助你思考，不用特别拘泥于这四个步骤：
- 问题拆解 我们要求解 str1(0,…m) 和 str2(0,…n) 的最长公共子序列，如果这是最终要求解的问题，那么它的子问题是什么呢？其实是 str1(0,…m-1) 和 str2(0,…n-1)，以及 str1(0,…m-1) 和 str2(0,…n)，还有 str1(0,…m) 和 str2(0,…n-1)，如果要找它们之间的关系，那我们需要思考一个问题就是，这些子问题怎么变成最终要求解的问题，当前的问题考虑当前字符是否相等，很直接的一个发现就是，如果 str1(m)==str2(n)，那么我们就可以将子问题中的 str1(0,…m-1) 和 str2(0,…n-1) 后面添加两个相同字符递进成当前问题；如果不相等，我们就需要考虑在三个子问题中选择一个较大值了。 说到这里，如果你还是不太清楚问题之间的联系，那我们一起来画画表格，熟悉一下这个过程： 题目求解 text1 = "abcde", text2 = "ace" 的最长公共子序列 "" a c e "" 0 0 0 0 a 0 如果其中一个字符串是空串 b 0 那么两个字符不存在公共子序列 c 0 对应的子问题状态初始化为 0 d 0 e 0 "" a c e "" 0 0 0 0 a 0 1 1 1 text1 = "a" text2 = "a" || text2 = "ac" || text2 = "ace" b 0 考虑当前状态 dp[i][j] 的时候 c 0 我们可以考虑子状态 dp[i – 1][j – 1] d 0 dp[i][j – 1] e 0 dp[i – 1][j] "" a c e "" 0 0 0 0 a 0 1 1 1 b 0 1 1 1 text1 = "ab" text2 = "a" || text2 = "ac" || text2 = "ace" c 0 d 0 e 0 "" a c e "" 0 0 0 0 a 0 1 1 1 b 0 1 1 1 c 0 1 2 2 text1 = "abc" text2 = "a" || text2 = "ac" || text2 = "ace" d 0 画到这里，不知道你有没有发现当当前的字符不相同时 e 0 dp[i][j] = Math.max(dp[i – 1][j], dp[i][j – 1]) "" a c e "" 0 0 0 0 a 0 1 1 1 b 0 1 1 1 c 0 1 2 2 d 0 1 2 2 text1 = "abcd" text2 = "a" || text2 = "ac" || text2 = "ace" e 0 "" a c e "" 0 0 0 0 a 0 1 1 1 b 0 1 1 1 c 0 1 2 2 d 0 1 2 2 e 0 1 2 3 text1 = "abcde" text2 = "a" || text2 = "ac" || text2 = "ace" 3 就是我们要返回的答案
- 状态定义
dp[i][j]表示的就是 str1(0,…i) 和 str2(0,…j) 的答案，基本上字符串匹配类动态规划都可以先尝试这样去定义状态 - 递推方程 在拆解问题中也说了，有两种情况，就是: 如果 str1(i) != str2(j): dp[i][j] = Math.max(dp[i – 1][j], dp[i][j – 1]) 如果 str1(i) == str2(j): dp[i][j] = Math.max(dp[i – 1][j], dp[i][j – 1], dp[i – 1][j – 1] + 1) 因为 dp[i – 1][j – 1] + 1 >= dp[i – 1][j] && dp[i – 1][j – 1] + 1 >= dp[i][j – 1] 所以第二项可以化简： 如果 str1(i) == str2(j): dp[i][j] = dp[i – 1][j – 1] + 1
- 实现 通常来说字符相关的问题可以把状态数组多开一格用来存放空串匹配的情况，这道题空串的情况答案都是 0，使用 Java 语言也不需要考虑初始化
参考代码
public int longestCommonSubsequence(String text1, String text2) { int length1 = text1.length(); int length2 = text2.length(); int[][] dp = new int[length1 + 1][length2 + 1]; char[] textArr1 = text1.toCharArray(); char[] textArr2 = text2.toCharArray(); for (int i = 1; i <= length1; ++i) { for (int j = 1; j <= length2; ++j) { if (textArr1[i - 1] == textArr2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[length1][length2]; }
LeetCode 第 72 号问题：编辑距离。
题目描述
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1:
输入: word1 = "horse", word2 = "ros" 输出: 3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
示例 2:
输入: word1 = "intention", word2 = "execution" 输出: 5 解释: intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
题目分析
求解编辑距离，也是经典老题，编辑距离其实在实际工作中也会用到，主要用于分析两个单词的相似程度，两个单词的编辑距离越小证明两个单词的相似度越高。
题目说可以通过增加字符，删除字符，以及 替换字符 这三个操作来改变一个字符串，并且每个操作的 cost 都是 1，问一个单词转换成另一个单词的最小 cost，老样子，四个步骤分析一遍：
- 问题拆解 我们考虑求解 str1(0…m) 通过多少 cost 变成 str2(0…n)，还是来看看它的子问题，其实还是三个
- str1(0…m-1) 通过多少 cost 变成 str2(0…n)
- str1(0…m) 通过多少 cost 变成 str2(0…n-1)
- str1(0…m-1) 通过多少 cost 变成 str2(0…n-1) 你可能会问你怎么这么快就写出子问题来，这些子问题是如何推导来的，它们和当前问题之间的联系又是什么？ 别急，听我慢慢道来。 一般字符匹配类问题的核心永远是两个字符串中的字符的比较，而且字符比较也只会有两种结果，那就是 相等 和 不相等，在字符比较的结果之上我们才会进行动态规划的统计和推导。 回到这道题，当我们在比较 str1(m) 和 str2(n) 的时候也会有两种结果，即 相等 或 不相等，如果说是 相等，那其实我们就不需要考虑这两个字符，问题就直接变成了子问题 str1(0…m-1) 通过多少 cost 变成 str2(0…n-1)，如果说 不相等，那我们就可以执行题目给定的三种变换策略:
- 将问题中的 str1 末尾字符 str1(m) 删除，因此只需要考虑子问题 str1(0…m-1)，str2(0…n)
- 将问题中的 str1 末尾字符 str1(m) 替换 成 str2(n)，这里我们就只需要考虑子问题 str1(0…m-1)，str2(0…n-1)
- 将问题中的 str1 末尾 添加 一个字符 str2(n)，添加后 str1(m+1) 必定等于 str2(n)，所以，我们就只需要考虑子问题 str1(0…m)，str2(0…n-1) 如果你还不是特别清楚问题之间的关系，那就画图表吧，这里我就略过。
- 状态定义 dp[i][j] 表示的是子问题 str1(0…i)，str2(0…j) 的答案，和常规的字符匹配类动态规划题目一样，没什么特别
- 递推方程 问题拆解那里其实说的比较清楚了，这里需要把之前的描述写成表达式的形式： str1(i) == str2(j): dp[i][j] = dp[i – 1][j – 1] tip: 这里不需要考虑 dp[i – 1][j] 以及 dp[i][j – 1]，因为 dp[i – 1][j – 1] <= dp[i – 1][j] +1 && dp[i – 1][j – 1] <= dp[i][j – 1] + 1 str1(i) != str2(j): dp[i][j] = Math.min(dp[i – 1][j], dp[i][j – 1], dp[i – 1][i – 1]) + 1 你可以看到字符之间比较的结果永远是递推的前提
- 实现 这里有一个初始化，就是当一个字符串是空串的时候，转化只能通过添加元素或是删除元素来达成，那这里状态数组中存的值其实是和非空字符串的字符数量保持一致。
参考代码
public int minDistance(String word1, String word2) { char[] arr1 = word1.toCharArray(); char[] arr2 = word2.toCharArray(); int[][] dp = new int[arr1.length + 1][arr2.length + 1]; dp[0][0] = 0; for (int i = 1; i <= arr1.length; ++i) { dp[i][0] = i; } for (int i = 1; i <= arr2.length; ++i) { dp[0][i] = i; } for (int i = 1; i <= arr1.length; ++i) { for (int j = 1; j <= arr2.length; ++j) { if (arr1[i - 1] == arr2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1; } } } return dp[arr1.length][arr2.length]; }
LeetCode 第 44 号问题：通配符匹配。
题目描述
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。 '*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1:
输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入: s = "aa" p = "*" 输出: true 解释: '*' 可以匹配任意字符串。
示例 3:
输入: s = "cb" p = "?a" 输出: false 解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:
输入: s = "adceb" p = "*a*b" 输出: true 解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:
输入: s = "acdcb" p = "a*c?b" 输入: false
题目分析
题目给定两个字符串，一个字符串是匹配串，除了小写字母外，匹配串里面还包含 * 和 ? 这两个特殊字符，另一个是普通字符串，里面只包含小写字母。
题目问这个普通字符串是否和匹配字符串相匹配，匹配规则是 ? 可以匹配单个字符，* 可以匹配一个区间，也就是多个字符，当然也可以匹配 0 个字符，也就是空串。
依然是四个步骤走一遍：
- 问题拆解 做多了，你发现这种问题其实都是一个套路，老样子，我们还是根据我们要求解的问题去看和其直接相关的子问题，我们需要求解的问题是 pattern(0…m) 和 str(0…n) 是否匹配，这里的核心依然是字符之间的比较，但是和之前不同的是，这个比较不仅仅是看两个字符相不相等，它还有了一定的匹配规则在里面，那我们就依次枚举讨论下： pattern(m) == str(n): 问题拆解成看子问题 pattern(0…m-1) 和 str(0…n-1) 是否匹配 pattern(m) == ?: 问题拆解成看子问题 pattern(0…m-1) 和 str(0…n-1) 是否匹配
``<br />pattern(m) == *:</p></li> <li><p>可以匹配空串、以及任意多个字符<br />当 * 匹配空串时：问题拆解成看子问题 pattern(0…m-1) 和 str(0…n) 是否匹配<br />当 * 匹配任意字符时：问题拆解成看子问题 pattern(0…m) 和 str(0…n-1) 是否匹配<br />``这里解释一下，匹配任意多个字符意味着之前的子问题也可以使用当前的，也就是用 pattern(m) 来进行匹配，因此，当前问题可以拆解成子问题 pattern(0…m) 和 str(0…n-1) 是否匹配，你发现弄来弄去，子问题依然是那三个： - pattern(0…m-1) 和 str(0…n-1) 是否匹配
- pattern(0…m-1) 和 str(0…n) 是否匹配
- pattern(0…m) 和 str(0…n-1) 是否匹配 不知道你是否发现了字符匹配类动态规划问题的共性，如果是画表格，你只需要关注当前格子的 左边、上边、左上 这三个位置的相邻元素，因为表格有实际数据做辅助，所以画表格有时可以帮助你找到问题与子问题之间的联系。
- 状态定义 还是老样子，dp[i][j] 表示的就是问题 pattern(0…i) 和 str(0…j) 的答案，直接说就是 pattern(0…i) 和 str(0…j) 是否匹配
- 递推方程 把之前 “问题拆解” 中的文字描述转换成状态的表达式就是递推方程： pattern(i) == str(j) || pattern(i) == '?': dp[i][j] = dp[i – 1][j – 1] pattern(i) == '*': dp[i][j] = dp[i – 1][j] || dp[i][j – 1]
- 实现 这类问题的状态数组往往需要多开一格，主要是为了考虑空串的情况，这里我就不赘述了。 我想说的是，关于初始化的部分，如果 str 是空的，pattern 最前面有
*，因为*是可以匹配空串的，因此这个也需要记录一下，反过来，如果 pattern 是空的，str 只要不是空的就无法匹配，这里就不需要特别记录。
参考代码
public boolean isMatch(String s, String p) { char[] sArr = s.toCharArray(); char[] pArr = p.toCharArray(); boolean[][] dp = new boolean[pArr.length + 1][sArr.length + 1]; dp[0][0] = true; for (int i = 1; i <= pArr.length; ++i) { if (pArr[i - 1] != '*') { break; } else { dp[i][0] = true; } } for (int i = 1; i <= pArr.length; ++i) { for (int j = 1; j <= sArr.length; ++j) { if (sArr[j - 1] == pArr[i - 1] || pArr[i - 1] == '?') { dp[i][j] = dp[i - 1][j - 1]; } else if (pArr[i - 1] == '*') { dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; } } } return dp[pArr.length][sArr.length]; }
LeetCode 第 97 号问题。
题目描述
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出: true
示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 输出: false
题目分析
题目的输入是三个字符串，问其中两个字符串是否能够交错合并组成第三个字符串，一个字符相对于其他字符的顺序在合并之后不能改变，这也是这道题的难点，不然的话你用一个哈希表就可以做了，三个字符串是否意味着要开三维的状态数组？还是四个步骤来看看：
- 问题拆解 在拆解问题之前，我们必须保证前两个字符串的字符的总数量必须正好等于第三个字符串的字符总数量，不然的话，再怎么合并也无法完全等同。这里有一个点，当我们考虑 str1(0…i) 和 str2(0…j) 的时候，其实第三个字串需要考虑的范围也就确定了，就是 str3(0…i+j)。如果我们要求解问题 str1(0…m) 和 str2(0…n) 是否能够交错组成 str3(0…m+n)，还是之前那句话，字符串匹配问题的核心永远是字符之间的比较：
- 如果 str1(m) == str3(m+n)，问题拆解成考虑子问题 str1(0…m-1) 和 str2(0…n) 是否能够交错组成 str3(0…m+n-1)
- 如果 str2(n) == str3(m+n)，问题拆解成考虑子问题 str1(0…m) 和 str2(0…n-1) 是否能够交错组成 str3(0…m+n-1) 你可能会问需不需要考虑子问题 str1(0…m-1) 和 str2(0…n-1)？ 在这道题目当中，不需要！ 千万不要题目做多了就固定思维了，之前说到这类问题可以试着考虑三个相邻子问题是为了让你有个思路，能更好地切题，并不是说所有的字符串匹配问题都需要考虑这三个子问题，我们需要遇到具体问题具体分析。
- 状态定义 dp[i][j] 表示的是 str1(0…i) 和 str2(0…j) 是否可以交错组成 str3(0…i+j)，这里再补充说明下为什么我们不需要开多一维状态来表示 str3，其实很简单，str3 的状态是由 str1 str2 决定的，str1 str2 定了，str3 就定了
- 递推方程 把之前问题拆解中的文字描述转换成状态的表达式就是递推方程： str1(i) == str3(i+j) dp[i][j] |= dp[i – 1][j] str2(j) == str3(i+j) dp[i][j] |= dp[i – 1][j]
- 实现 初始化的时候需要考虑单个字符串能否组成 str3 对应的区间，这个比较简单，直接判断前缀是否相等即可。
参考代码：
public boolean isInterleave(String s1, String s2, String s3) { int length1 = s1.length(); int length2 = s2.length(); int length3 = s3.length(); if (length1 + length2 != length3) { return false; } boolean[][] dp = new boolean[length1 + 1][length2 + 1]; dp[0][0] = true; char[] sArr1 = s1.toCharArray(); char[] sArr2 = s2.toCharArray(); char[] sArr3 = s3.toCharArray(); for (int i = 1; i <= length1; ++i) { dp[i][0] = dp[i - 1][0] && sArr1[i - 1] == sArr3[i - 1]; } for (int i = 1; i <= length2; ++i) { dp[0][i] = dp[0][i - 1] && sArr2[i - 1] == sArr3[i - 1]; } for (int i = 1; i <= length1; ++i) { for (int j = 1; j <= length2; ++j) { if (sArr3[i + j - 1] == sArr1[i - 1]) { dp[i][j] |= dp[i - 1][j]; } if (sArr3[i + j - 1] == sArr2[j - 1]) { dp[i][j] |= dp[i][j - 1]; } } } return dp[length1][length2]; }
总结
字符匹配类动态规划的问题还有挺多，比如 Regular Expression、Distinct Subsequence 等等，这些问题都非常的经典，它们的难度都不低，但是这类问题其实是有套路的，首先状态特别好找，另外拆解问题也有一定的规律。
如果还是没有思路，那就画画表格吧，考虑当前格子的时候，看看其 左边，上边，左上边 这三个格子所代表的子问题的状态，有实际数据作为辅助，问题之间的递进关系相对来说会比较好找些。这些问题大多在 LeetCode 上面标的都是 hard 难度，弄清楚了这些套路后，回过头去看看推导过程，然后再看看二、三十行的代码量，不知道是否能给你一些新的感悟和认识？
