动态规划：字符串匹配
各位小伙伴大家好~本周我们来介绍两道字符串相关的题目，主要是使用动态规划来进行匹配解题。
在开始之前，我们聊一聊动态规划。其实动态规划看到底也是属于穷举算法。我们将所有的可能性都列举出来，然后在所有的可能性中选择一个最优解即可。但是同样是穷举，为啥我们使用迭代的时候容易超时呢？主要在于动态规划带有一定的记忆。当我们使用迭代的时候，有很多子问题被我们重复计算，但是动态规划却将每一次的子问题进行了一个简单的存储，类似于备忘录。当遇到子问题的时候，我们先到备忘录中寻找之前有没有遇到过相同的子问题，如果遇到过，那么我们就直接从备忘录中取出结果返回即可。这样就可以有效避免对子问题的重复计算，大大提升效率。
所以一般遇到最值问题，或者多种可能性，选择最优解的时候，我们可以往动态规划上去想。下面我们来分享两道题目。
编辑距离
❝LeetCode72 --- 编辑距离【困难】
题目描述
❞
1、解题思路
根据题目，为了匹配字符串，我们需要将其中一个字符串修改为另一个字符串，其中的操作主要有3种，替换，插入，和删除。我们需要找到最少的修改次数。
由于属于求最值问题，需要遍历所有的可能，所以我们首选动态规划。
-
关于数组的定义：
-
定义 dp[i][j]，将其表示为word1的前i个字符修改为word2的前j个字符时，所使用的最少次数； -
关于初始化:
-
第一列
dp[i][0]表示word2为空的时候，那么我们将全部采取删除操作，所以此时对于dp[i][0] = i; -
第二列
dp[0][j]表示word1为空时，我们将全部采取插入操作，对word1使用插入来达到最后的目标字符串，所以dp[0][j]=j; -
关于状态方程：
-
如果
word1[i] == word2[j]，那么此时，我们是不需要进行任何操作的，所以次数也是等于两个字符串上一次修改的次数，即dp[i][j] = dp[i-1][j-1]。 -
当两个字符串的字符不相同时，我们就可以对其选择进行题目中的三种操作：
-
替换：替换之后的字符串将会与 word1[i-1]和word2[j-1]的字符串相同，所以对应的dp[i][j] = dp[i-1][j-1]+1; -
插入：插入之后的字符串将会与 word1[i]和word2[j-1]的字符串相同，所以对应的dp[i][j] =dp[i][j-1]+1； -
删除：删除之后的字符串将会与 word1[i-1]和word2[j]的字符串相同，所以对应的dp[i][j] =dp[i-1][j]+1；
对于三种操作，我们进行对比，选出最小值即可得到从word1[i]到word2[j]的最小修改次数dp[i][j]。
于是我们就可以进行动态规划的代码编写了~
2、代码实现
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length() +1][word2.length() + 1];
//代表着当word2 == " " 时，需要将word1中的每个字母逐个删除，将 word1 改造成为 word2
for(int i = 1 ; i <= word1.length() ; i++){
dp[i][0] += i;
}
//代表当word1 == " " 时，需要逐个进行插入，得到一个 word2
for(int j = 1 ; j <= word2.length() ; j++){
dp[0][j] += j;
}
for(int i = 1 ; i <= word1.length() ; i++ ){
for(int j = 1 ; j <= word2.length() ; j++){
if(word1.charAt(i-1) == word2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])) + 1;
}
}
}
return dp[word1.length()][word2.length()];
}
通配符匹配
❝LeetCode44 --- 通配符匹配【困难】
题目描述
❞
1、解题思路
这道题目，依然是两个字符串，需要我们来记录两者是否能够相互匹配。那么我们还是需要列举出所有的情况，那么我们还是优先考虑动态规划。
有了上面的编辑距离的铺垫，我们这次的类比应该会简单一点。
-
定义数组
dp[i][j]： -
将其申明为Boolean类型数组，定义 dp[i][j]表示s[i]和p[j]的匹配情况。 -
下面对其进行初始化：
-
dp[0][0]：表示当s和p都为空时，两者匹配成功，所以dp[0][0] = true； -
第一列：表示当p为空时，
s[i]与p的匹配状态，此时当然全部都为false -
第一行：表示当s为空时，
p[j]与s的匹配状态，在这种情况下，只有p[j]之前的所有的字符均为星号时，才可以匹配成功。
3.状态方程：
-
当
s[i] = p[j]时，此时的状态应该与s[i-1]和p[j-1]的状态相同，所以此时dp[i][j] = dp[i-1][j-1]; -
当
p[j] = '*'时，此时的星号可以匹配一个空串，那么dp[i][j] = dp[i][j-1]，同时也可以匹配多个字符串，此时dp[i][j] = dp[i-1][j]，而我们只需要有一种能够匹配成功即可，所以dp[i][j] = dp[i][j-1] || dp[i-1][j]。 -
当上面的两种情况都不满足时，就代表当前的两种状态是不匹配的，所以
dp[i][j]=false;
2、代码实现
public boolean isMatch(String s, String p) {
int sLen = s.length();
int pLen = p.length();
boolean[][] dp = new boolean[sLen+1][pLen+1];
//初始化,当s和p都为空的时候，为匹配成功
dp[0][0] = true;
//当s不为空，p为空时，dp[i][0]都为fasle
//当p的每个字符否为星号时，才可以对空串s匹配成功
for(int j = 1 ; j <= pLen ; j++){
dp[0][j] = dp[0][j-1] && p.charAt(j-1) == '*';
}
for(int i = 1 ; i <= sLen ; i++){
for(int j = 1 ; j <= pLen ; j++){
if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?'){
dp[i][j] = dp[i-1][j-1];
}else if(p.charAt(j-1) == '*'){
//此时表示将星号匹配前一个字符，或者匹配空串
dp[i][j] = (dp[i-1][j] || dp[i][j-1]);
}
}
}
return dp[sLen][pLen];
}