串換位算法

Question

假設有給出了兩個字符串：

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

這裏我們交流T和H.我有興趣寫代碼，其對許多變化是如何就要從一個字符串轉換到另一個字符串的位置。

Answer 1

假設距離計數只是交換，這裏是一個基於排列的想法，它運行在線性時間。

該算法的第一步是確保兩個字符串在其字符內容中真正等效。這可以使用哈希表（或覆蓋所有字母表的固定數組）在線性時間內完成。如果它們不是，則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需要一個證明...我沒有在網上找到它。

Answer 2

有幾個edit distance算法，給定的Wikipeida鏈接有幾個鏈接。

Answer 3

你的問題並不是那麼容易，因爲在計算交換之前，你需要確保每次交換都會減少這兩個字符串之間的「距離」（在等式中）。然後，實際上你會尋找計數，但你應該尋找最小的計數（或者至少我想），否則存在無限的方式來交換一個字符串來獲得另一個。

您應該首先檢查哪些字符已經就位，然後對於每個看不到字符的字符是否有可交換的字符，以便減少字符串之間的下一個距離。然後迭代，直到完成該過程。

如果你不想有效地做到這一點，但只需計算掉期次數，就可以使用一個位陣列，其中1對於每個位置良好的字符都是1，否則0。你會完成時，每一位是1。