牛客对应题目链接:添加字符_牛客笔试题_牛客网 (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 的长度 - 相同位数,就可以得到不相同的位数了。