Why not login to Qiita and try out its useful features?

We'll deliver articles that match you.

You can read useful information later.

0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

基本情報:小学生でもわかる?アナグラム判定アルゴリズム

Posted at

試験対策で新しい問題集を進めたところ、コードの意味と動きがわからない問題がありました。

アナグラム判定プログラムですが、簡単ながらハマリました。

問題:問題文は実行できません。

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に格納されている数字を1する!という単純な処理になります。

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

以上参考になれば幸いです。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up

Qiita Advent Calendar is held!

Qiita Advent Calendar is an article posting event where you post articles by filling a calendar 🎅

Some calendars come with gifts and some gifts are drawn from all calendars 👀

Please tie the article to your calendar and let's enjoy Christmas together!

0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?