Source: InterviewBit – Anagrams

Given an array of strings, return all groups of strings that are anagrams. Represent a group by a list of integers representing the index in the original list. Look at the sample case for clarification.

Anagram : a word, phrase, or name formed by rearranging the letters of another, such as 'spar', formed from 'rasp'

Note: All inputs will be in lower-case. 

Example :

Input : cat dog god tca
Output : [[1, 4], [2, 3]]

cat and tca are anagrams which correspond to index 1 and 4.
dog and god are another set of anagrams which correspond to index 2 and 3.
The indices are 1 based ( the first element has index 1 instead of index 0).

Ordering of the result : You should not change the relative ordering of the words / phrases within the group. Within a group containing A[i] and A[j], A[i] comes before A[j] if i < j.

解題：

這題要求把字母組合相同的單字（或是一串亂打的字串）分類在一起並依序列大小排列輸出。為了簡化程式碼，筆者在解題時套了內建模組 collections.Counter 以簡化計算字母數的程式碼架構；而完成字母計數後便可以將組合相同的字分類在一起，這裡為方便組合筆者亦使用內建模組 collections.defaultdict 將所有即將建立的字典value值均預設為陣列以利後續將相同組合的序列值擺在一起。

這裡需要注意的是依據字母出現的順序不同，即使相同組合的字典其 dict.items() 也可能不同，故在比對之前需要先進行對 dict.items() 的排序以確保相同組合的資料排列方式必定一致；另外則是字典的 key 值必須是 hashable ，故須將排序後之 dict.items() 轉為 tuple 格式。

最後則是因字典的資料輸出時並無法確保其依資料建立時序排序，故最後的輸出值仍需另外執行排序確保輸出值符合題目要求。

Code:

from collections import defaultdict, Counter
class Solution:
    # @param A : tuple of strings
    # @return a list of list of integers
    def anagrams(self, A):
        output = []
        anagramDict = defaultdict(list)
        for i in range(len(A)):
            counter = tuple(sorted(Counter(A[i]).items()))
            anagramDict[counter].append(i+1)
        for val in anagramDict.values():
            output.append(val)
        return sorted(output)

GitHub: GitHub

發表留言