目次
解いた問題
leetcode 242 Valid Anagram
2つの文字列s,tが与えられるから、それらがアナグラムならTrueを返してねって問題。
アナグラムとはある文字列の文字を並び替えて、別の文字列を作ること、またはその関係にある文字列同士のこと、らしいです。
学び
- 辞書型の扱いについて
- 頻度確認では
dict[key] = dict.get(key, default) + 1を使うと1行で済む。 - 辞書の一致確認には
dict_a == dict_bでよい。キーとバリューの組み合わせを自動で見てくれる
- 頻度確認では
- 空間計算量は「入力サイズnが増えたときに、追加で必要になるメモリ量がどう増えるか」である
-
for文を使ってもメモリ量が変わらないこともあるので要確認
-
最初に考えた解法
文字の長さが一致してないならFalse、単語の出現数がそれぞれ一致していたらTrue、違ったらFalse返せばいいのではと考えた。
ハッシュマップつくってキーに文字、バリューに出現数保持してそれぞれを比較することを考える。
単純に考えるとfor文2つでs,tそれぞれ回してハッシュマップに入れることを思いつくが、時間計算量が$O(n^2)$になるので、$O(n)$になるよう、長さを先に見て一致していたら片方の長さ分forを回してインデックス指定で中身を取り出すことに。
空間計算量が$O(s+t) = O(n)$オーダーとなりコスパ悪そうに見えるが改善策が思いつかないのでいったん実装。
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
hashmap_s = {}
hashmap_t = {}
for i in range(len(s)):
hashmap_s[s[i]] = hashmap_s.get(s[i], 0) + 1
hashmap_t[t[i]] = hashmap_t.get(t[i], 0) + 1
if hashmap_s == hashmap_t:
return True
return False
上記で正解。
ハッシュマップは解法自体思いつくようになってきていて成長を感じる。
しかし空間計算量を見ると$O(1)$だった。
空間計算量
forの中でs[i]などで保持しているが、それぞれが追記される形でなく、1周につき1文字のみを保持する形なので$O(n)$ではないっぽい。
正解
自分で作ったものが最適解かもな～と思いつつ調べたら下記のようになった。
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
count = [0] * 26
for i in range(len(s)):
count[ord(s[i]) - ord('a')] += 1
count[ord(t[i]) - ord('a')] -= 1
for c in count:
if c != 0:
return False
return True
ordが完全初見で何が何やら分からないので調べてみた。
ordとは
Python標準関数の一つで、1文字をその文字に対する数値=Unicodeコードポイントに変換するものらしいです。
Unicodeとは世界中の文字・記号を、1つの共通ルール（番号）で扱うための国際規格で、アルファベットにはaから順番に97,98,...と割り当てられていて、z = 122となっている。
具体例は下記のようになる。
uni_a = ord("a")
print(uni_a) # 97
ちなみにordはordinalの略で、「順序を表す」「順番の」という意味。
count[ord(s[i]) - ord('a')] += 1の意味
countは26個の0が並んでいる配列。
count[ord...]は[...]がインデックスを表して、配列の何番目かを全体で表す。
それにたいして+= 1なので、count[...]に該当する要素をインクリメントしている。
下の処理は-=のデクリメントをする処理となっている。
[...]の中身を深ぼるとord(s[i])は入力文字列のインデックスに合う1文字を指定してunicode化。
ord("a")は文字列aをunicode化して97という値を取っている。
したがって、入力文字列が英語26文字のどれかであるという制約をうまく使って26個要素のある配列を生み出し、aを基準にそれぞれのアルファベットを0,1,2,...,25という文字と対応づけて、そのインデックスの要素をインクリメント、デクリメントしている。
| 入力文字 | 計算 | インデックス |
|---|---|---|
a |
97 - 97 | 0 |
b |
98 - 97 | 1 |
| ... | ... | ... |
z |
122 - 97 | 25 |
全体として何をしているのか
インクリメント、デクリメントをすると、アナグラムの場合countはすべての要素が0に戻るはずなのでif c != 0で中身調べて、すべて0ならTrue、それ以外はFalseを返しているって感じ。
感想
いや～おもろい。
まさかunicodeを使って計算するとは思わなかった。
日本語等複雑な文字が入るとhashmapが最適解の一種らしいが、英語小文字のみに限るとオーバーヘッドの少なさからリストを使ったものが最適解になるそう。
分からないが分かる、というのはやはりおもろい。
それが手軽に味わえるアルゴリズムはやっぱりおもろい。
転職時のコーディング面接対策にやり始めましたが今のところ単なる趣味としてやってます。
今後もゆるゆる楽しみます。