試験対策で新しい問題集を進めたところ、コードの意味と動きがわからない問題がありました。
アナグラム判定プログラムですが、簡単ながらハマリました。
問題：問題文は実行できません。
class map:
def __init__(self):
self.dict = {}
def put(self, key, value):
self.dict[key] = value
def get(self, key):
return self.dict.get(key, None)
def equals(self, other_map):
return self.dict == other_map.dict
def chkanag(str1, str2):
map1 = map()
map2 = map()
if len(str1) != len(str2):
return False
for i in range(len(str1)):
# for str1
if map1.get(str1[i]) is None:
map1.put(str1[i], 1)
else:
map1.put(**問題A**)
# for str2
if map2.get(str2[i]) is None:
map2.put(str2[i], 1)
else:
map2.put(**問題B**)
return map1.equals(map2)
# テスト
print(chkanag("free", "reef")) # True
print(chkanag("hello", "world")) # False
答え
問題A：str1[i], map1.get(str1[i]) + 1
問題B：str2[i], map2.get(str2[i]) + 1
答えを見てもいまいち意味が分かりません。
このmap1.put(str1[i], map1.get(str1[i]) + 1)は何をしているのでしょうか。
アナグラムのアルゴリズムの開設
アナグラムのアルゴリズムは複数ありますが、こちらはClassを使いmapという配列に文字を格納して行うアルゴリズムです。
引数Aと引数Bの文字数が同じ場合に限り、各mapに文字の種類とその文字の出現回数を格納していき、引数Aと引数Bの文字の種類と出現回数が同じだった場合、アナグラムが成立します。
よくよく問題文を読めば回答できる問題でしたね(';')
コード解説：
map1,map2ってなに？
文字と文字の出現回数を格納する配列です。
a,b,cだったら、
a:1 b:1 c:1
というキー文字と文字の発生数が格納されます。
getとputって？
- putは引数をもとに配列に格納する
- getはその文字の発生回数を加算していくために使われます。
if map1.get(str1[i]) is None:
map1.put(str1[i], 1)
というif文では、そのi番目の文字がmapに格納されていないか確認して、
格納されていない場合、文字を入れます。
今回は最初のa:1をmap1に格納します。
else:
map1.put(str1[i], map1.get(str1[i]) + 1)
map1.get(str1[i]) + 1
という処理では、mapにすでに文字が格納されている場合、その文字のmapに格納されている数字を１する！という単純な処理になります。
a,a,bを呼び出した場合、
a:2 b1になるということです。
if map2.get(str2[i]) is None:
map2.put(str2[i], 1)
else:
map2.put(str2[i], map2.get(str2[i]) + 1)
でもstr2で同じ処理を繰り返します。
この関数をstr1[a,a,b] str2[b,a,b]で処理するとします。
上記の処理で、map1[a:2,b:1] map2[a:2,b:1]になります。
equalsの処理
こちらの関数は、文字の数さえ合っていれば、配列の順番にかかわらず、「true」を吐き出します。
動くコード
class map:
def __init__(self):
self.dict = {}
def put(self, key, value):
self.dict[key] = value
def get(self, key):
return self.dict.get(key, None)
def equals(self, other_map):
return self.dict == other_map.dict
def chkanag(str1, str2):
map1 = map()
map2 = map()
if len(str1) != len(str2):
return False
for i in range(len(str1)):
# for str1
if map1.get(str1[i]) is None:
map1.put(str1[i], 1)
else:
map1.put(str1[i], map1.get(str1[i]) + 1)
# for str2
if map2.get(str2[i]) is None:
map2.put(str2[i], 1)
else:
map2.put(str2[i], map2.get(str2[i]) + 1)
return map1.equals(map2)
# テスト
print(chkanag("reef", "free")) # True (anagram)
print(chkanag("hell", "leff"))#false
以上参考になれば幸いです。