动态规划：字符串匹配---鹏-程-万-里

各位小伙伴大家好~本周我们来介绍两道字符串相关的题目，主要是使用动态规划来进行匹配解题。

在开始之前，我们聊一聊动态规划。其实动态规划看到底也是属于穷举算法。我们将所有的可能性都列举出来，然后在所有的可能性中选择一个最优解即可。但是同样是穷举，为啥我们使用迭代的时候容易超时呢？主要在于动态规划带有一定的记忆。当我们使用迭代的时候，有很多子问题被我们重复计算，但是动态规划却将每一次的子问题进行了一个简单的存储，类似于备忘录。当遇到子问题的时候，我们先到备忘录中寻找之前有没有遇到过相同的子问题，如果遇到过，那么我们就直接从备忘录中取出结果返回即可。这样就可以有效避免对子问题的重复计算，大大提升效率。

所以一般遇到最值问题，或者多种可能性，选择最优解的时候，我们可以往动态规划上去想。下面我们来分享两道题目。

编辑距离

❝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]; } ---来自腾讯云社区的---鹏-程-万-里