anagram字符串編輯距離算法/代碼？

Question

有兩個字謎串S和P.有兩個基本操作：

1. 交換兩個字母都在附近，例如在BCCAB交換「A」和「C」，費用爲1
2. SWAP的第一個字母和字符串中的最後一個字母，成本是1

問題：設計一個高效的算法，最小的成本變化看，以P.

我嘗試了貪心算法，但我找到了反例，我想它 是不正確的。我知道着名的DP問題編輯距離，但我沒有得到這個的公式。

任何人都可以幫助嗎？一個想法和僞代碼會很棒。

Answer 1

我不知道http://en.wikipedia.org/wiki/A * _search_algorithm會算作效率嗎？對於啓發式，請查找每個角色必須走的最小距離，將字符串視爲圓，並將這些距離的總和除以2。在圓上，每個角色需要參與足夠的交換，以便一步一步地將其移動到目的地，並且每個交換隻影響兩個字符，因此該啓發式應該是所需交換次數的下限。

Answer 2

如果沒有結束交換，答案很簡單：你必須得到第一個和最後一個字母，而且以後再也不能「保存」了。因此，一個字一個_我其中0 <= i < n你想「泡」正確的一個和地方 _N-1，然後重複對這個詞的_我其中1 <= i < n-1直到你留下了0或1個字母。

由於有兩個方向，每個字母都可以到達正確的位置，所以使用端部交換選項時，會留下更難的問題。基本上在源詞和目標詞之間有一個二分圖，並且您希望找到一個匹配來最小化距離總和。即使這不算算法，因爲每個交換都會移動兩個字母，而不僅僅是一個。底線是，您可能必須進行搜索，但至少您可以將搜索綁定到無端交換距離。