题目简述
输入两个字符串 \(S\) 和 \(T\)，将他们进行如下操作：
- 将 \(S\) 字符串的第一位删掉，放在任意一位。
问最少多少次以后可以让 \(S\) 和 \(T\) 相等。
思路简述
看到这个题目以后，第一个想到的就是搜索，暴力搜一遍。但是仔细想来倒也不用这么麻烦，只需要特判一下就可以。
如果两个字符串连字母个数都不一样直接输出 \(-1\)。
否则只需要从 \(T\) 的末尾向首位遍历并与 \(S\) 比较。
-
如果一样，就不用加，只需要将
index--继续向前遍历。 -
如果不一样，就直接
sum++将次数加 \(1\) 就可以了，最后sum的值就是次数。
代码实现
#include<iostream>
using namespace std;
string s1,s2;//两个字符串 S 和 T。
int n,t1[105],t2[105];//t1 和 t2 分别存储 S 和 T 中的26个字母各自出现了几次 。
int main(){
cin>>n;
cin>>s1>>s2;
//记录 S 中26个字母各自出现了几次 。
for(int i=0;i<n;i++)
t1[int(s1[i]-'a')]++;
//记录 T 中26个字母各自出现了几次。
for(int i=0;i<n;i++)
t2[int(s2[i]-'a')]++;
//如果两个字符串连字母个数都不一样，就说明不行。
for(int i=0;i<26;i++){
if(t1[i]!=t2[i]){
cout<<"-1\n";
return 0;
}
}
int index=n-1,sum=0;//index是 T 的下标，sum 是操作次数
for(int i=n-1;i>=0;i--){//从后往前遍历
if(s1[index]!=s2[i])
sum++;//如果不一样就将 sum++ 增加操作次数
else index--;//一样就说明两个字符一样，就不用移动。继续将 T 向前遍历即可
}
cout<<sum<<"\n";
return 0;
}