字符串怎麼樣才能改?設A和B是兩個字符串我們要用最少的字符操作次數,将字符串A轉換為字符串B這裡所說的字符操作共有三種:,今天小編就來聊一聊關于字符串怎麼樣才能改?接下來我們就一起去研究一下吧!
![字符串怎麼樣才能改(字符串的修改) 字符串怎麼樣才能改(字符串的修改)1](/uploads0/70cFvnSh_Q1YnxGkpoWK1HF6hhy/it/u=3673361361,2737580234&fm=253&gp=0.jpg)
字符串怎麼樣才能改
ICPC--1206: 字符串的修改題目描述設A和B是兩個字符串。我們要用最少的字符操作次數,将字符串A轉換為字符串B。這裡所說的字符操作共有三種:
\1. 删除一個字符; \2. 插入一個字符; \3. 将一個字符改為另一個字符。 對任給的兩個字符串A和B,計算出将字符串A變換為字符串B所用的最少字符操作次數。
輸入第一行為字符串A;第二行為字符串B;字符串A和B的長度均小于200。
輸出隻有一個正整數,為最少字符操作次數。
樣例輸入
sfdxbqw
gfdgw
4
#include<bits/stdc .h>
using namespace std;
int main(){
int dp[210][210];
char a[210], b[210];
int i, j, len1, len2;
scanf("%s", a);
scanf("%s", b);
len1 = strlen(a);
len2 = strlen(b);
for (i = 0; i <= len1; i )
dp[i][0] = i;
for (i = 0; i <= len2; i )
dp[0][i] = i;
for (i = 1; i <= len1; i ){
for (j = 1; j <= len2; j ){
if (a[i-1] == b[j-1])//相同
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = min(min(dp[i - 1][j] 1, dp[i][j - 1] 1), dp[i - 1][j - 1] 1);
}
}
cout << dp[len1][len2] << endl;
return 0;
}