LeetCode "49. Group Anagrams"にPythonで挑んだ話

自分には、setを使いたがるという悪い手癖が付いているようです。
setを使うやり方を思いついた時には、代案も考えるようにします。

#方針１

キーを整数、値を空の集合とした辞書を作ります。
各キーごとに、そこが空の集合なら、手元にある文字列を文字に分解してその集合に入れます。また、そのインデックスの答えにも格納します。
そこがすでに要素のある集合なら、その集合と、手元にある文字列を文字に分解した集合との、和集合を作ります。
その和集合がもともとの要素と長さが変わらないなら、同じ文字列で構成されていると考え、そのインデックスの答えに格納します。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        n = len(strs)
        
        if n <= 1:
            return [strs]
        
        sets = {i : set() for i in range(n)}
        ans = [[] for _ in range(len(strs))]
        
        for str_ in strs:
            for i in range(n):
                if len(ans[i]) == 0:
                    ans[i].append(str_)
                    sets[i] |=  set(str_)
                    break

                union = set(str_) | sets[i] 
                if len(union) == len(sets[i]):
                    ans[i].append(str_)
                    sets[i] |=  set(str_)
                    break
        
        return [inner_list for inner_list in ans if len(inner_list) >= 1]

結果：Wrong Answer

同じ文字を一部で使った異なる文字列の長さのものに対応していなかったので、誤りです。
また、おそらく同じ文字を複数回使った文字列にも対応していないです。

#方針2
辞書の内容が同じ文字列を持っているか否かの判定のために、setの特徴を使うのをやめます。
代わりに、キーを文字列、値をその文字列を整列させたものの辞書を作り、それを利用して比較します。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

        n = len(strs)
        
        if n <= 1:
            return [strs]
        
        sorted_strs = [''.join(sorted(list(str_))) for str_ in strs]
        sorted_str_dict = {sorted_str_ : [] for sorted_str_ in sorted_strs}

        for str_ in strs:
            sorted_str_ = ''.join(sorted(list(str_)))
            sorted_str_dict[sorted_str_].append(str_)

        ans = [value for value in sorted_str_dict.values() if len(value) >= 1]        	

        return ans

結果：Success

やったぜ！