s and t are two strings.
Change string s into string t in the least steps.
In each step you can insert or delete a char of the string.
INPUT n1 s
n2 t
n1 is the length of string s
n2 is the length of string t
OUT the least steps
exp:
INPUT 4 abcd
6 aefbhd
OUT 4
#include<iostream>
#include<string>
using namespace std;
string s1,s2;
int map[100];
int i,j,result[100];
int n1,n2,nc;
int main(){
cin>>n1>>s1>>n2>>s2;
nc=0;
for (i=0;i<n1;i++){
if ((j=s2.find(s1[i]))>=0){
map[nc]=j;
s2.replace(j,1," ");
nc++;
}
}
result[nc-1]=1;
for (i=nc-2;i>=0;i--){
for (j=i+1;j<nc;j++) if ((map[i]<map[j])&&(result[i]<result[j])) result[i]=result[j];
result[i]++;
}
j=0;
for (i=0;i<nc;i++) if(result[i]>j) j=result[i];
cout<<n1+n2-j-j;
system("pause");
return 0;
}