Problem
2つの文字列が与えられ、その２つがアナグラムかどうか (文字の順序を変えて、別の単語になる)を判定するプログラムを書くという問題です。
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
InputとOutputの例は次になります。
Input: s = "anagram", t = "nagaram"
Output: true
Key Idea
2つの解法が考えられます。
一つはHashmap (Dictionary)を利用する方法、もう一つはSortを利用する方法です。
最後に、面接では使えないが実務的には有効な方法も紹介します。
Approach #1 : Hashmap
{a:3, n:1, g:1, m:1} といったように、文字列をdictionaryに変換した後に比較する方法です。get関数を使うと、dictionaryにkeyが存在しなくてもerrorではなく Noneや指定した値を返してくれるのでスッキリとしたコードにすることができます。
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s)!= len(t):
return False
d1, d2 = dict(), dict()
for i in range(len(s)):
d1[s[i]] = 1 + d1.get(s[i], 0)
# 上記のようにgetを使った一文は、下記のif文と同じ挙動です
# if s[i] in d1:
# d1[s[i]] += 1
# else:
# d1[s[i]] = 1
d2[t[i]] = 1 + d2.get(t[i], 0)
for key, value in d1.items():
if d2.get(key) != value:
return False
return True
この解法では、計算量は下記の様になります。
-
Time complexity: O(n)。各文字列を1回だけ走査します。n は文字列の長さです。
-
Space complexity: O(1)。問題文中に文字列sとtはアルファベットという制約があるため、O(1)となります。
ただし、Follow up questionで言及されているように、sとtがUnicodeの全範囲の文字を含む可能性があるとすると、最悪のシナリオでは、sとtがすべて異なる文字から成る場合、ハッシュマップのサイズは文字列の長さに比例します。したがって、このようなシナリオでは、Space complexityはO(n)となります。
Approach #2 : Sorting
2つの文字列がアナグラムであるためには、文字列をソートした場合、同じ文字列になるはずです。
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return sorted(s) == sorted(t)
Sortingの計算量は、言語や関数に依存します。Pythonのsorted関数は、Timsortというアルゴリズムを使用しており、最悪ケースでもTime complexity がO(nlogn)、Space complexityがO(n)となることが保証されています。
Approach #3 : Counter
Counterクラスを利用する方法は、アナグラムの定義を考えると直感的な方法です。Interviewでは適切ではないかもしれませんが、実務においては有用です。Counter('mississippi') と実行すると、Counter({'i': 4, 's': 4, 'p': 2, 'm': 1}) に変換されます
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return Counter(s) == Counter(t)
実際、Leetcodeのテストケースを実行すると、Approach #1, #2よりも良いRuntime, Memory performanceの結果になりました。