关于两个字符串的匹配转化问题
最近遇到好几个这种类型的问题，主要就是给你两个字符串，然后进行字符串自己的匹配或者转化，这类问题就是采用动态规划，二维的和一维的，现在对这一类问题做一个总结
题目一[leetcode72]https://leetcode.com/problems/edit-distance/
给了两个字符串word1和word2，使用删除，添加，替换操作从word1转化到word2，每个操作代价为1，需要找到最小代价的转化方法。
算法原理&算法步骤
方法一：二维dp
使用一个二维的数组dp[][]，其中dp[i+1][j+1]表示word1[0,i]转化到word2[0,j]需要的最小代价，那么现在来求解动态规划方程
考虑现在word1[i]和Word2[j],
如果word1[i]=word2[j],那么dp[i+1][j+1]=dp[i][j]
否则word1[i]！=word2[j]时，有这么几种情况
1. abcd abce 替换 dp[i+1][j+1]=dp[i][j]
2.abc abcd 添加 dp[i+1][j+1]=dp[i+1][j]
3.adcd abd 删除 dp[i+1][j+1]=dp[i][j+1]
有了上述动态规划的方程，接下来的问题就简单多了
需要特别注意的是dp[][]数组的第一行和第一列的初始化
第一行表示word1取了""，那么dp[0][j+1]=j+1(添加操作)
第一列表示word2去了""，那么dp[i+1][0]=i+1(删除操作)
代码：
public class Solution {
public int minDistance(String word1, String word2) {
int len1=word1.length();
int len2=word2.length();
int[][] dp=new int[len1+1][len2+1];//dp[i+1][j+1]表示word1[0,i],word2[0,j]的cnovert需要进行的编辑次数
for(int j=0;j<len2;j++){
dp[0][j+1]=j+1;
}
for(int i=0;i<len1;i++){
dp[i+1][0]=i+1;
}
for(int i=0;i<len1;i++){
for(int j=0;j<len2;j++){
if(word1.charAt(i)==word2.charAt(j)){
dp[i+1][j+1]=dp[i][j];
}
else{
dp[i+1][j+1]=Math.min(dp[i][j],Math.min(dp[i][j+1],dp[i+1][j]))+1;
//abcc abcd abcd abc abc abcd
}
}
}
return dp[len1][len2];
}
}
方法二：一维dp
现在回过头来看看二维动态规划方程,
dp[i+1][j+1]=dp[i][j]，word1[i]=word2[j]
dp[i+1][j+1]=min(dp[i][j],dp[i+1][j],dp[i][j+1])
dp[i+1][j+1]只与dp[i][j]、dp[i+1][j]、dp[i][j+1]有关，由于计算顺序也是一行一行的来，所以可以考虑进行复用，只使用一个一维的数组dp,但是假设在计算j-1的时候就更新了dp[j ]，那么 上一行的dp[j]就不见了，在计算dp[j+1]的时候是需要上一行的dp[j]的，所以这里之前先不更新，在计算了dp[j+1]之后再去更新dp[j]，并且用一个变量prev记忆dp[j],这样
dp[j+1]=dp[j]，word1[i]=word2[j]
dp[j+1]=min(dp[j],dp[j+1],prev) word1[i]!=word2[j]，
其中dp[j+1]代表当前行j位置，dp[j]代表上一行j-1位置，prev代表当前行j-1位置
也是需要注意的是，word1取""的时候，也就是dp最开始的初始化
还有word2取""，也就是求解每一行的时候开始的时候的prev的初始化。
另外一点，由于dp[j+1]是在下一列才更新，所以最后一列在循环中没有得到更新，在一行计算完成后，需要给dp[word2.length]=prev单独赋值
public class Solution {
public int minDistance(String word1, String word2) {
int len1=word1.length();
int len2=word2.length();
int[] dp=new int[len2+1];
for(int j=0;j<len2;j++){
dp[j+1]=j+1;
}
int prev;
int cur;
for(int i=0;i<len1;i++){
prev=i+1;
for(int j=0;j<len2;j++){
if(word1.charAt(i)==word2.charAt(j))
cur=dp[j];
else{
cur=Math.min(dp[j+1],Math.min(dp[j],prev))+1;
}
dp[j]=prev;
prev=cur;
}
dp[len2]=prev;
}
return dp[len2];
}
}
题目二
[leetcode10]https://leetcode.com/problems/regular-expression-matching/
表达式匹配，给了字符串s和p,需要对s和p进行匹配,其中p的"."表示任意一个字符,p中的"*"，表示0个或多个前边的字符
算法原理&算法步骤
同样是使用一个二维动态规划数组dp[][]，其中dp[i+1][j+1]表示s[0,i],p[0,j]时候能够匹配,那么现在来求解动态规划方程
假如s[i]==p[j]||p[j]=='.' 那么 dp[i+1][j+1]=dp[i][j]
否则，如果p[j]=='*'，如果s[i]!=p[j-1]&&p[j-1]!='.',直接抛弃a*，dp[i+1][j+1]=dp[i+1][j-1]
否则，表明当前位置p s不同，前一个位置可以匹配，那么有以下几种可能
abc abc* 直接抛弃* dp[i+1][j+1]=dp[i+1][j]
abcd abc* *代表一个或多个字符 dp[i+1][j+1]=dp[i][j+1]
abcccc abc* *把前边一个也拿走 dp[i+1][j+1]=dp[i+1][j-1]
至此，动态规划方程已经得到
同样第一行的初始化，代表s为""p只有为aA这样的才可以匹配。
而第一列的话，如果p为空的话是一定不能匹配的，所以默认为false.
代码：
public class Solution {
public boolean isMatch(String s, String p) {
if(s==null||p==null)
return false;
boolean[][] dp=new boolean[s.length()+1][p.length()+1];//dp[i][j]表示以i-1为结尾位置的s子串和以j-1为结尾位置的p子串是否能够match
dp[0][0]=true;
for(int j=0;j<p.length();j++){//s取出子串为“”，如果p 1*2*3*这样子类型就能够匹配
if(p.charAt(j)=='*'&&dp[0][j-1])
dp[0][j+1]=true;
}
for(int i=0;i<s.length();i++){
for(int j=0;j<p.length();j++){
if(p.charAt(j)=='.'||p.charAt(j)==s.charAt(i)){
dp[i+1][j+1]=dp[i][j];
}
else if(p.charAt(j)=='*'){
if(p.charAt(j-1)!='.'&&p.charAt(j-1)!=s.charAt(i)){//直接丢弃前边一个字符 a*之间被丢弃
dp[i+1][j+1]=dp[i+1][j-1];
}
else{
//aaa a*
dp[i+1][j+1]=dp[i+1][j]||dp[i+1][j-1]||dp[i][j+1];//abc abc* abcc*
//a* 当做a 当做“” 当做多个a(注意这里不能是dp[i][j]这样的话就只是当做了一个a)
}
}
}
}
return dp[s.length()][p.length()];
}
}
第三题
[leetcode44]https://leetcode.com/problems/wildcard-matching/
同上题大同小异，这次"?"代表任意一个字符，"*"代表任意一个字符序列，可以为空。
方法一:dp解法
和上一题一样的思路，而且分析比上一题简单多，所以这里不再详述
public class Solution {
public boolean isMatch(String s, String p) {
if(s==null||p==null)
return false;
boolean[][] dp=new boolean[s.length()+1][p.length()+1];
dp[0][0]=true;
for(int j=0;j<p.length();j++){
if(p.charAt(j)=='*'&&dp[0][j])
dp[0][j+1]=true;
}
for(int i=0;i<s.length();i++){
for(int j=0;j<p.length();j++){
if(p.charAt(j)==s.charAt(i)||p.charAt(j)=='?')
dp[i+1][j+1]=dp[i][j];
else if(p.charAt(j)=='*'){
dp[i+1][j+1]=dp[i+1][j]||dp[i][j+1];
// 直接去除* *代替一个或多个其他字符
}
}
}
return dp[s.length()][p.length()];
}
}
方法二：
由于这里和前边的元素没有关系了，所以如果前面出现了不匹配，那么直接就可以判定不匹配，不需要就行后边的操作，所以直观上，上述动态规划的方法就存在很大的时间浪费，这里看到一种更有效率的方法。本质思想就是遇到之后，你走不通了那么这一段走不通的都丢给*来代替。
public class Solution {
public boolean isMatch(String str, String pattern) {
if(str==null||pattern==null)
return false;
int s=0;
int p=0;
int match=0;//*所代表的范围的结尾
int starIdx=-1;//*的位置
while(s<str.length()){
if(p<pattern.length()&&(pattern.charAt(p)=='?'||pattern.charAt(p)==str.charAt(s))){
s++;
p++;
}
else if(p<pattern.length()&&pattern.charAt(p)=='*'){
starIdx=p;
match=s;
p++;//s不增加，因为有可能*代表空
}
else if(starIdx!=-1){
p=starIdx+1;
match++;
s=match;
}else{
return false;
}
}
while(p<pattern.length()&&pattern.charAt(p)=='*'){//如果后边都是*的话，可以当做什么也没有
p++;
}
return p==pattern.length();
}
}
题目四：
[leetcode97]https://leetcode.com/problems/interleaving-string/
给了三个字符串str1 str2 str3 str3是不是str1和str2的交叉
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int len1=s1.length();
int len2=s2.length();
int len3=s3.length();
if(len1+len2!=len3)
return false;
boolean[][] dp=new boolean[len1+1][len2+1];//dp[i+1][j+1]表示s1[0,i] s2[0,j]时候满足条件交接到s3[0,i+j+1]
dp[0][0]=true;
for(int j=0;j<len2;j++){
if(s2.charAt(j)==s3.charAt(j))
dp[0][j+1]=true;
else
break;
}
for(int i=0;i<len1;i++){
if(s1.charAt(i)==s3.charAt(i))
dp[i+1][0]=true;
else
break;
}
char c1;
char c2;
char c3;
for(int i=0;i<len1;i++){
c1=s1.charAt(i);
for(int j=0;j<len2;j++){
c2=s2.charAt(j);
c3=s3.charAt(i+j+1);
if(c1==c3&&c2==c3)
dp[i+1][j+1]=dp[i][j+1]||dp[i+1][j];
else if(c2==c3)
dp[i+1][j+1]=dp[i+1][j];
else if(c1==c3)
dp[i+1][j+1]=dp[i][j+1];
}
}
return dp[len1][len2];
}
}
题目五
[leetcode115]https://leetcode.com/problems/distinct-subsequences/
一个字符串中包含多少个另一个字符串
public class Solution {
public int numDistinct(String s, String t) {
int len1=s.length();
int len2=t.length();
int[][] dp=new int[len1+1][len2+1];
dp[0][0]=1;
for(int i=0;i<len1;i++){
dp[i+1][0]=1;
}
for(int i=0;i<len1;i++){
for(int j=0;j<len2;j++){
if(s.charAt(i)==t.charAt(j)){
dp[i+1][j+1]=dp[i][j]+dp[i][j+1];
}
else
dp[i+1][j+1]=dp[i][j+1];
}
}
return dp[len1][len2];
}
}
public class Solution {
public int numDistinct(String s, String t) {
int len1=s.length();
int len2=t.length();
int[] dp=new int[len2+1];
int prev;
int cur;
for(int i=0;i<len1;i++){
dp[0]=1;
prev=1;
char c=s.charAt(i);
for(int j=0;j<len2;j++){
if(t.charAt(j)==c){
cur=dp[j+1]+dp[j];
}
else
cur=dp[j+1];
dp[j]=prev;
prev=cur;
}
dp[len2]=prev;
}
return dp[len2];
}
}
