如何組字符串是一個編輯距離

-2

arr1 = ["ABC", "ABD", "ABCD", "ABCE", "ACCE", "AB"]

我想組這些字符串放到子列表，使得每個子表將只包含爲x字符串離開距離。例如，通過用別的東西替換一個字母可以找到距編輯一段距離的字符串。所以對於上面的列表，我想生產：

arr2 = [["ABC", "ABD"], ["ABCD", "ABCE", "ACCE"], ["AB"]]

在文獻中是否有算法來解決這個問題？什麼是解決這個問題的有效方法？

編輯：我定義的編輯距離與以下意義有點不同：只允許替換x個字母（如果x = 1，只有1個字母可以不同），不能添加或刪除。

來源

2014-06-12 user3733188

我能想到的唯一的事情就是遍歷一個雙循環，其中對於內循環中的每個項目，我一次更改一個字符並與外循環中的值進行比較，但顯然這不是一個聰明/高效的方法。 – user3733188

這個問題沒有很好的定義，因爲單編輯距離不是傳遞屬性。 'arr1 = [「ABC」，「ABD」，「EBC」]'的預期輸出是什麼？無論如何，代替兩個嵌套循環，使用一個循環遍歷'arr1'和'set'來執行查找，這使得你從O（n^2）到O（n log n）。 –

我可能會錯過一些東西，但這不是按照它們的長度來分組嗎？如果我只能做一個編輯，這意味着我要麼洗牌的字母（長度保持不變），要麼添加或刪除字母，在這種情況下，長度將被改變 - 所以只有那些是_same length_將相同的編輯訂單帶走，對嗎？ –

通過你的例子可能不是最終會被你所尋找的算法暗示的算法，但它肯定可以：

editdist = lambda a, b: sum(0 if c1 == c2 else 1 for (c1, c2) in zip(a, b)) 
a = ["ABC", "ABD", "ABCD", "ABCE", "ACCE", "AB"] 
a = list(reversed(a)) 
ret = [] 
while a: 
    s = a.pop() 
    for sublist in ret: 
     if len(sublist[-1]) == len(s) and editdist(sublist[-1], s) == 1: 
      sublist.append(s) 
      s = None 
      break 
    if s: ret.append([s]) 
print ret

的代碼假設你想要的結果在你的問題：字符串這樣的序列序列中的每個字符串與它之前和之後的字符串相距一個編輯距離。

來源

2014-06-12 10:36:17

您可以用每個字符串作爲頂點構建一個圖。如果相應的字符串距離x編輯距離，則在兩個頂點之間存在邊緣。現在，只需運行DFS遍歷即可獲得所需的分組。

讓我知道你是否需要更多的細節。

來源

2014-06-13 00:09:51 knsn1994

如何組字符串是一個編輯距離

回答

相關問題