我們給了兩個小寫拉丁字母序列。它們的長度相同，給定類型的字母數量相同（第一個字母與第二個字母具有相同數量的t，依此類推）。我們需要找到將第一個序列轉換為第二個序列所需的最少交換次數（“交換”是指更改兩個相鄰字母的順序）。我們可以安全地假設每兩個序列可以相互轉換。我們可以用蠻力來做到這一點，但是序列太長了。輸入：序列的長度（至少2個，最大999999），然后是兩個序列。輸出：一個整數，表示序列變得相同所需的交換次數。示例：{5，aaaaa，aaaaa}應該輸出{0}，{4，abcd，acdb}應該輸出{2}。我想到的第一件事是冒泡。我們可以簡單地對排序每個交換的序列進行冒泡排序。問題是：a）是O（n ^ 2）最壞的情況b）我不相信在每種情況下它都會給我最小的數字...即使是優化的冒泡現象也似乎并不能解決問題。我們可以實施雞尾酒解決方案來解決烏龜的問題-但這會給我帶來最佳表現嗎？也許有更簡單/更快的東西？這個問題也可以表述為：當唯一允許的操作是移調時，如何確定兩個字符串之間的編輯距離？