最近遇到好幾個(gè)這種類型的問題，主要就是給你兩個(gè)字符串，然后進(jìn)行字符串自己的匹配或者轉(zhuǎn)化，這類問題就是采用動(dòng)態(tài)規(guī)劃，二維的和一維的，現(xiàn)在對這一類問題做一個(gè)總結(jié)
題目一[leetcode72]https://leetcode.com/problems/edit-distance/
給了兩個(gè)字符串word1和word2，使用刪除，添加，替換操作從word1轉(zhuǎn)化到word2，每個(gè)操作代價(jià)為1，需要找到最小代價(jià)的轉(zhuǎn)化方法。
算法原理&算法步驟
方法一：二維dp
使用一個(gè)二維的數(shù)組dp[][]，其中dp[i+1][j+1]表示word1[0,i]轉(zhuǎn)化到word2[0,j]需要的最小代價(jià)，那么現(xiàn)在來求解動(dòng)態(tài)規(guī)劃方程
考慮現(xiàn)在word1[i]和Word2[j],
如果word1[i]=word2[j],那么dp[i+1][j+1]=dp[i][j]
否則word1[i]！=word2[j]時(shí)，有這么幾種情況
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]
有了上述動(dòng)態(tài)規(guī)劃的方程，接下來的問題就簡單多了
需要特別注意的是dp[][]數(shù)組的第一行和第一列的初始化
第一行表示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需要進(jìn)行的編輯次數(shù)
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
現(xiàn)在回過頭來看看二維動(dòng)態(tài)規(guī)劃方程,
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]有關(guān)，由于計(jì)算順序也是一行一行的來，所以可以考慮進(jìn)行復(fù)用，只使用一個(gè)一維的數(shù)組dp,但是假設(shè)在計(jì)算j-1的時(shí)候就更新了dp[j ]，那么 上一行的dp[j]就不見了，在計(jì)算dp[j+1]的時(shí)候是需要上一行的dp[j]的，所以這里之前先不更新，在計(jì)算了dp[j+1]之后再去更新dp[j]，并且用一個(gè)變量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]代表當(dāng)前行j位置，dp[j]代表上一行j-1位置，prev代表當(dāng)前行j-1位置
也是需要注意的是，word1取""的時(shí)候，也就是dp最開始的初始化
還有word2取""，也就是求解每一行的時(shí)候開始的時(shí)候的prev的初始化。
另外一點(diǎn)，由于dp[j+1]是在下一列才更新，所以最后一列在循環(huán)中沒有得到更新，在一行計(jì)算完成后，需要給dp[word2.length]=prev單獨(dú)賦值
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/
表達(dá)式匹配，給了字符串s和p,需要對s和p進(jìn)行匹配,其中p的"."表示任意一個(gè)字符,p中的"*"，表示0個(gè)或多個(gè)前邊的字符
算法原理&算法步驟
同樣是使用一個(gè)二維動(dòng)態(tài)規(guī)劃數(shù)組dp[][]，其中dp[i+1][j+1]表示s[0,i],p[0,j]時(shí)候能夠匹配,那么現(xiàn)在來求解動(dòng)態(tài)規(guī)劃方程
假如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]
否則，表明當(dāng)前位置p s不同，前一個(gè)位置可以匹配，那么有以下幾種可能
abc abc* 直接拋棄* dp[i+1][j+1]=dp[i+1][j]
abcd abc* *代表一個(gè)或多個(gè)字符 dp[i+1][j+1]=dp[i][j+1]
abcccc abc* *把前邊一個(gè)也拿走 dp[i+1][j+1]=dp[i+1][j-1]
至此，動(dòng)態(tài)規(guī)劃方程已經(jīng)得到
同樣第一行的初始化，代表s為""p只有為aA這樣的才可以匹配。
而第一列的話，如果p為空的話是一定不能匹配的，所以默認(rèn)為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為結(jié)尾位置的s子串和以j-1為結(jié)尾位置的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)){//直接丟棄前邊一個(gè)字符 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* 當(dāng)做a 當(dāng)做“” 當(dāng)做多個(gè)a(注意這里不能是dp[i][j]這樣的話就只是當(dāng)做了一個(gè)a)
}
}
}
}
return dp[s.length()][p.length()];
}
}
第三題
[leetcode44]https://leetcode.com/problems/wildcard-matching/
同上題大同小異，這次"?"代表任意一個(gè)字符，"*"代表任意一個(gè)字符序列，可以為空。
方法一: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];
// 直接去除* *代替一個(gè)或多個(gè)其他字符
}
}
}
return dp[s.length()][p.length()];
}
}
方法二：
由于這里和前邊的元素沒有關(guān)系了，所以如果前面出現(xiàn)了不匹配，那么直接就可以判定不匹配，不需要就行后邊的操作，所以直觀上，上述動(dòng)態(tài)規(guī)劃的方法就存在很大的時(shí)間浪費(fèi)，這里看到一種更有效率的方法。本質(zhì)思想就是遇到之后，你走不通了那么這一段走不通的都丟給*來代替。
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;//*所代表的范圍的結(jié)尾
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不增加，因?yàn)橛锌赡?代表空
}
else if(starIdx!=-1){
p=starIdx+1;
match++;
s=match;
}else{
return false;
}
}
while(p<pattern.length()&&pattern.charAt(p)=='*'){//如果后邊都是*的話，可以當(dāng)做什么也沒有
p++;
}
return p==pattern.length();
}
}
題目四：
[leetcode97]https://leetcode.com/problems/interleaving-string/
給了三個(gè)字符串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]時(shí)候滿足條件交接到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/
一個(gè)字符串中包含多少個(gè)另一個(gè)字符串
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];
}
}
