串换位算法

假设有给出了两个字符串：串换位算法

String s1= "MARTHA" 
String s2= "MARHTA"

这里我们交流T和H.我有兴趣写代码，其对许多变化是如何就要从一个字符串转换到另一个字符串的位置。

来源

2010-06-19 dato datuashvili

家庭作业标签，也许？ – KevenK 2010-06-19 14:42:41

哦哇，110个问题，3个答案，只有6个upvotes？ – KevenK 2010-06-19 14:43:26

假设距离计数只是交换，这里是一个基于排列的想法，它运行在线性时间。

该算法的第一步是确保两个字符串在其字符内容中真正等效。这可以使用哈希表（或覆盖所有字母表的固定数组）在线性时间内完成。如果它们不是，则s2不能被认为是s1的置换，并且“交换计数”是不相关的。

第二步计算将s2转换为s1所需的最小交换次数。这可以通过检查对应于从s1到s2的转换的置换p来完成。例如，如果s1 =“abcde”和s2 =“badce”，则p =（2,1,4,3,5），意味着位置1包含元素＃2，位置2包含元素＃1等。排列可以在线性时间内分解为permutation cycles。例子中的周期是（2,1）（4,3）和（5）。最小交换次数是每个周期所需交换的总次数。长度为k的周期需要k-1次交换才能“修复”。因此，交换次数是N-C，其中N是字符串长度，C是周期数。在我们的例子中，结果是2（交换1,2和3,4）。

现在，有两个问题在这里，我想我太累了，现在解决这些问题:)

1）我的解决方案假定没有字符是重复的，这是情况并非总是如此。需要进行一些调整才能正确计算交换计数。

2）我的公式＃MinSwaps = N-C需要一个证明...我没有在网上找到它。

来源

2010-06-19 23:04:15

有几个edit distance算法，给定的Wikipeida链接有几个链接。

来源

2010-06-19 14:42:47 Donnie

这些都只考虑掉换。 – IVlad 2010-06-19 15:04:34

你的问题并不是那么容易，因为在计算交换之前，你需要确保每次交换都会减少这两个字符串之间的“距离”（在等式中）。然后，实际上你会寻找计数，但你应该寻找最小的计数（或者至少我想），否则存在无限的方式来交换一个字符串来获得另一个。

您应该首先检查哪些字符已经就位，然后对于每个看不到字符的字符是否有可交换的字符，以便减少字符串之间的下一个距离。然后迭代，直到完成该过程。

如果你不想有效地做到这一点，但只需计算掉期次数，就可以使用一个位阵列，其中1对于每个位置良好的字符都是1，否则0。你会完成时，每一位是1。

来源

2010-06-19 14:47:47 Jack

这确保了交换的最小数量如何？如果你只是盲目地交换元素，或者至少在没有完成字符串转换的死胡同中，你最终会陷入无限循环。 – IVlad 2010-06-19 15:03:55

迭代约束是为了减少字符串之间的距离。如果你确保每一步都缩短了距离，你怎么能在无限循环中结束？它可以卡住，确保这两个字符串不是“交换平等”，但它确保不循环而不做任何事情。该方法称为_greedy_，确保如果保留局部最优（通过每次迭代减少距离和广告），则全局最优是一个直接后果。 – Jack 2010-06-19 15:50:00

然后我假设我们正在谈论两个项目'i'和'j'的交换，其中不存在像'i = j + 1'这样的约束或反之亦然。另外，因为OP没有说相邻掉期，而只是掉期。 – Jack 2010-06-19 15:54:05

回答

相关问题