假设有两个字符串:
String s1= "MARTHA"
String s2= "MARHTA"
这里我们交换T和H的位置.我有兴趣编写代码,计算从一个String转换到另一个String所需的更改次数.
假设距离仅计算交换，这是一个基于排列的想法，它在线性时间内运行。
该算法的第一步是确保两个字符串的字符内容确实相等。这可以使用哈希表（或覆盖所有字母表的固定数组）在线性时间内完成。如果不是，则 s2 不能被视为 s1 的排列，并且“交换计数”是无关紧要的。
第二步计算将 s2 转换为 s1 所需的最小交换次数。这可以通过检查与从 s1 到 s2 的变换相对应的排列 p 来完成。例如，如果 s1="abcde" 且 s2="badce"，则 p=(2,1,4,3,5)，意味着位置 1 包含元素 #2，位置 2 包含元素 #1，等等。排列可以在线性时间内分解成排列循环。示例中的循环是 (2,1) (4,3) 和 (5)。最小交换次数是每个周期所需交换的总数。长度为 k 的循环需要 k-1 次交换才能“修复它”。因此，交换次数为 NC，其中 N 是字符串长度，C 是循环次数。在我们的示例中，结果是 2（交换 1,2，然后交换 3,4）。
现在，这里有两个问题，我想我现在太累了，无法立即解决它们:)
1）我的解决方案假设没有字符重复，但情况并非总是如此。需要进行一些调整才能正确计算交换计数。
2）我的公式#MinSwaps=NC需要证明...我在网上没有找到它。