牛客对应题目链接：添加字符_牛客笔试题_牛客网 (nowcoder.com)
一、分析题目
简单的两层 for 循环暴力枚举。
二、代码
//值得学习的代码 #include <iostream> #include <string> using namespace std; string a, b; int main() { cin >> a >> b; int m = a.size(), n = b.size(); int ret = m; for(int i = 0; i <= n - m; i++) // 枚举 b 的起始位置 { int tmp = 0; for(int j = 0; j < m; j++) { if(a[j] != b[i + j]) { tmp++; } } ret = min(tmp, ret); } cout << ret << endl; return 0; }
三、反思与改进
这道题目的正确思路并不复杂，就是一个简单的两层 for 循环暴力枚举（可以通过题目所给的数据量大胆尝试）。我原先用的是双指针来写这道题目，遇到不同的字符就 diff++，然后指向字符串 b 的指针就往后移动一步（排除头尾两部分），但只能通过 60% 的测试用例，还是想复杂了，其实本质上就是求最大重合字符的个数。
注意：除了短的字符串内部不能更换，两边的都可以添加成重复字符，所以结果就是字符串 a 的长度 - 相同位数，就可以得到不相同的位数了。
