コレは個人の備忘録です、この記事の情報を参考に場合はしっかりとしたソースのチェックをお願いします
お疲れ様です。steveです。最近毎日leetcodeを解いています。
昨日も例に漏れず、同じ大学のON先輩とleetcodeを解いていました。neetcodeのロードマップにしたがった有用問題をgptに選抜してもらい。その日は久々のmediumの問題でした。
こんな問題です。
Given an array of strings strs, group the
anagrams
together. You can return the answer in any order.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Explanation:
There is no string in strs that can be rearranged to form "bat".
The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.
同じアナグラムをリストでグループ分けした、グループのリストを返すらしいです。
自分の発想としては、
{"eat":{a:1,e,1,t,1},
"tea":{a:1,e,1,t,1},
"tan":{a:1,n:1,t:1}
・・・}
というオブジェクトを作成して
maps =
{{a:1,e,1,t,1}:["eat","ate","tea"],
{a:1,n:1,t:1}:["nat","tan"],
・・・
}
result = list(maps.values())
とすればいけるかな？
と思っていました。
結果は・・・
TypeError: unhashable type: 'dict'
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
if values_list[i] in temp_total:
Line 26 in groupAnagrams (Solution.py)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ret = Solution().groupAnagrams(param_1)
Line 69 in _driver (Solution.py)
_driver()
Line 84 in <module> (Solution.py)
unhashableってなんだろう・・・
辞書（dict）のキーに関する制約
Pythonでは、辞書（dict）のキーとして使用できるオブジェクトは ハッシュ可能 でなければなりません。ハッシュ可能性とは、次の2つの条件を満たすことを指します：
1,ハッシュ値を持つ:
オブジェクトが固定された一意のハッシュ値（hash() メソッド）を持つ必要があります。
ハッシュ値はオブジェクトが同じなら一貫している必要があります。
2,不変性:
オブジェクトが変更可能（ミュータブル）でない必要があります。ミュータブルなオブジェクトの場合、ハッシュ値がオブジェクトの状態によって変化するため、ハッシュテーブル（辞書やセット）での整合性が保てなくなります。
(gptより)
要は、dictのキーにdictを持ってこようっとしたことがいけなかったポイです。
ここで、問題になる、dictのキーの性質ですが、dictのキーは「一意に定まる」必要があります。
ですので、例えば
hashmap = {"a":1,"b":2,"c":3}
という構造は、それぞれキーが異なるオブジェクトなので、問題ありません。
例：
id("a") #140732487488816
id("b") #140732487488848
id("c") #140732487488880
→idが異なる
ので、一つのidに対してオブジェクトが保証されています。
ですが
hashmap = {[1,2,3]:b,[1,2,3,4]:c}
という構造は、キーが同じ可能性があり、一意に定まるオブジェクトと断言できません
例えば
ex_list = [1,2,3]
print(id(ex_list))
# 235948574589
ex_list.qppend(4) #この時点で、ex_list = [1,2,3,4]
print(id(ex_list))
# 235948574589
つまり、同じ id = 235948574589
でも、異なるリストを表現できるというわけです。
→この構造では、一つのidに対して一意に定まる とは言えません。
したがって、一つのidに対して一意に定まる ことを期待しているdictのキーに対して
このようなデータ構造を持つオブジェクトは格納できないのです
このように、同じidでも可変であるデータ構造をミュータブル と言います
逆に、一つのidに対して、一つのオブジェクトが保証されているデータ構造を、イミュータブルと言います
| 1 | 2 | 3 |
|---|---|---|
| 特徴 | ミュータブル（mutable） | イミュータブル（immutable） |
| 変更可能性 | 内容を変更可能 | 内容を変更不可 |
| IDの変化 | 変更してもIDは変わらない | 変更できないため新しいオブジェクトが作られる |
| 例 | list, dict, set | int, float, str, tuple |
なので、今回の問題は
maps =
{((a:1),(e,1),(t,1)):["eat","ate","tea"],
((a:1),(n:1),(t:1)):["nat","tan"],
・・・
}#キーをタプルにしている
のようにしないと、参照できないようです。
こういうプログラミングの根本となるデータ構造を勉強できたのは、いい体験でした。
今となっては、先に、inputのリストをソートしてから構造作成したほうが楽だと思います