两个等长字符串的最少替换次数等于其汉明距离,即对应位置字符不同的个数;长度不等时无法仅靠替换达成一致。

要使两个等长字符串通过字符替换操作变得完全相同,所需的最少替换次数,等于它们在对应位置上字符不同的个数,也就是汉明距离(Hamming Distance)。
核心判断逻辑
仅当两个字符串长度相等时,才有意义计算“最少替换次数”。若长度不同,无法仅靠替换达成一致(必须涉及插入/删除),此时问题性质改变,不属于纯替换范畴。
对于等长字符串 $a 和 $b,遍历每个索引 i,统计满足 $a[$i] !== $b[$i] 的位置数量即可。
PHP 实现方式(推荐)
使用内置函数高效、简洁:
立即学习“PHP免费学习笔记(深入)”;
-
count_chars($a ^ $b, 1):利用异或特性,相同字符异或结果为\0,不同则非零;count_chars(..., 1)返回各字节出现次数的关联数组,去掉\0后求和即为差异数 - 更直观写法:
strlen($a) - substr_count($a ^ $b, "\0")—— 异或后统计\0个数,总长减去相同位置数 = 不同位置数
简单示例
例如:$a = "abcd"; $b = "abxd";
逐位比较:
a==a → 相同
b==b → 相同
c!=x → 不同(计 1)
d==d → 相同
→ 最少替换次数为 1
注意事项
- 区分大小写:PHP 字符串比较默认区分大小写,
"A"和"a"视为不同 - 多字节字符(如中文)需用
mb_*函数处理,否则按字节操作可能出错;若确定是 ASCII 或单字节编码(如 ISO-8859-1),普通索引安全 - 空字符串之间距离为 0;两字符串完全相同时距离也为 0











