學點演算法之字元串的亂序檢查

原文：學點演算法之字元串的亂序檢查

問題

字元串的亂序檢查。

一個字元串是另一個字元串的亂序。如果第二個字元串只是第一個的重新排列，例如，』heart』 和 『earth』 就是亂序字元串。』python』 和 『typhon』 也是。為了簡單起見，我們假設所討論的兩個字元串具有相等的長度，並且他們由 26 個小寫字母集合組成。我們的目標是寫一個布爾函數，它將兩個字元串做參數並返回它們是不是迴文。

解法1:檢查

我們對亂序問題的第一個解法是檢查第一個字元串是不是出現在第二個字元串中。如果可以檢驗到每一個字元，那兩個字元串一定是迴文。可以通過用 None 替換字元來完成檢查。但是，由於 Python 字元串是不可變的，所以第一步是將第二個字元串轉換為列表。第一個字元串中的每個字元可以通過檢查在第二個列表中檢查元素是否存在，如果存在，替換成 None。

def anagramSolution1(s1,s2): alist = list(s2) pos1 = 0 stillOK = True while pos1 < len(s1) and stillOK: pos2 = 0 found = False while pos2 < len(alist) and not found: if s1[pos1] == alist[pos2]: found = True else: pos2 = pos2 + 1 if found: alist[pos2] = None else: stillOK = False pos1 = pos1 + 1 return stillOKprint(anagramSolution1(abcd,dcba))

s1 的每個字元都會在 s2 中進行最多 n 個字元的迭代

s2 列表中的 n 個位置將被訪問一次來匹配來自 s1 的字元。訪問次數可以寫成 1 到 n 整數的和，可以寫成

當 n 變大，n^2 這項佔據主導，1/2 可以忽略。所以這個演算法複雜度為 O(n^2 )。

解法2:排序和比較

另一個解決方案是利用這麼一個事實，即使 s1,s2 不同，它們只有由完全相同的字元組成，它們才是迴文。所以，如果我們按照字母順序排列每個字元串，從 a 到 z，如果兩個字元串相同，則這兩個字元串為迴文。

def anagramSolution2(s1,s2): alist1 = list(s1) alist2 = list(s2) alist1.sort() alist2.sort() if alist1 == alist2: return True else: return Falseprint(anagramSolution2(abcde,edcba))

這個演算法比較簡單，只用到了排序演算法，那麼排序演算法的複雜度還是多少呢？

在這裡找到了答案

python中的sorted演算法，網上有人撰文，說比較低級。其實不然，通過閱讀官方文檔，發現python中的sorted排序，真的是高大上，用的Timsort演算法。什麼是Timsort，請看 wiki的解釋：http://en.wikipedia.org/wiki/Timsort

另外，國內有一個文檔，適當翻譯：http://blog.csdn.net/yangzhongblog/article/details/8184707，這裡截取一個不同排序演算法比較的圖示，就明白sorted的威力了。

從時間複雜度來看，Timsort是威武的。

從空間複雜度來講，需要的開銷在數量大的時候會增大。

解法3: 窮舉法

解決這類問題的強力方法是窮舉所有可能性。

對於迴文檢測，我們可以生成 s1 的所有亂序字元串列表，然後查看是不是有 s2。這種方法有一點困難。當 s1 生成所有可能的字元串時，第一個位置有 n 種可能，第二個位置有 n-1 種，第三個位置有 n-3 種，等等。總數為 n?(n?1)?(n?2)?...?3?2?1n?(n?1)?(n?2)?...?3?2?1， 即 n! 。

雖然一些字元串可能是重複的，程序也不可能提前知道這樣，所以他仍然會生成 n! 個字元串。

所以當然不會採取這種方案了。

解法4: 計數和比較

我們最終解決迴文的方法是利用兩個亂序字元串具有相同的 a, b, c 等等的事實。

我們首先計算的是每個字母出現的次數。由於有 26 個可能的字元，我們就用 一個長度為 26 的列表，每個可能的字元佔一個位置。每次看到一個特定的字元，就增加該位置的計數器。最後如果兩個列表的計數器一樣，則字元串為亂序字元串。

def anagramSolution4(s1,s2): c1 = [0]*26 c2 = [0]*26 for i in range(len(s1)): pos = ord(s1[i])-ord(a) c1[pos] = c1[pos] + 1 for i in range(len(s2)): pos = ord(s2[i])-ord(a) c2[pos] = c2[pos] + 1 j = 0 stillOK = True while j<26 and stillOK: if c1[j]==c2[j]: j = j + 1 else: stillOK = False return stillOKprint(anagramSolution4(apple,pleap))

同樣，這個方案有多個迭代，但是和第一個解法不一樣，它不是嵌套的。兩個迭代都是 n, 第三個迭代，比較兩個計數列表，需要 26 步，因為有 26 個字母。一共 T(n)=2n+26T(n)=2n+26，即 O(n)，我們找到了一個線性量級的演算法解決這個問題。

如果讓我自己來選擇，我可能會選第二種，第二種最簡單，也最好理解。但是最後的結論表明 解法4 才是最優解法，排序固然簡單，但是但數量很大的時候，可能遠不止我們想的那麼簡單。

在結束這個例子之前，我們來討論下空間花費，雖然最後一個方案在線性時間執行，但它需要額外的存儲來保存兩個字元計數列表。換句話說，該演算法犧牲了空間以獲得時間。

很多情況下，你需要在空間和時間之間做出權衡。這種情況下，額外空間不重要，但是如果有數百萬個字元，就需要關注下。作為一個計算機科學家，當給定一個特定的演算法，將由你決定如何使用計算資源。

如有錯誤，請指出

圖片來源

各位下期見，不聊了，又該搬磚了。。。

感興趣可以來關注我的公眾號：zhangslob

推薦閱讀：