LeetCode 242. Valid Anagram
はじめに
LeetCode 「242. Valid Anagram」の問題をGoで解きました。
問題
問題文
Given two strings s and t, return true if t is an anagram* of s, and false otherwise.
*An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.
和訳
2つの文字列 s と t が与えられた場合、t が s のアナグラム*であれば true を返し、そうでない場合は false を返します。
*アナグラムとは、別の単語または句の文字を並べ替えて、元の文字をすべて 1 回だけ使用して形成される単語または句です。
例
Input: s = "anagram", t = "nagaram"
Output: true
Input: s = "rat", t = "car"
Output: false
制約
- 1 <= s.length, t.length <= 5 * 104
- s and t consist of lowercase English letters.
解答1
2つの文字列がアナグラムか判定する問題です。
ポイントは、それぞれの文字が何個あるかという点です。
まずは、キーがbyte・バリューがintのマップを作り、sの中の文字の数を記録する方法を考えました。
コード
func isAnagram(s string, t string) bool {
sLen := len(s)
tLen := len(t)
if sLen != tLen {
return false
}
byteCount := make(map[byte]int)
for i := range sLen {
byteCount[s[i]]++
}
for j := range tLen {
if byteCount[t[j]] == 0 {
return false
}
byteCount[t[j]]--
}
return true
}
この解答は汎用性が高く、Unicode文字にも対応しやすいです。
補足
for i := range 数値という書き方は、go1.22 から可能です。
それ以前の場合は、for i := 0; i < sLen; i++という形で記述する必要があります。
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(1)
- 使われる文字が英小文字（最大26種類）に限られており、O(1)とみなせる
解答2
解答1と考え方は同じですが、マップではなくint型のスライスを使用して実装することも可能です。
制約から、使用される文字は英語の小文字アルファベットだけなので、最大で26個です。
index 0 が a、1 が b...というように記録していくことにより、解答1と同じように処理することが可能です。
s[i] - 'a'の処理で、a~z を 0~25 に対応させています。
コード
func isAnagram(s string, t string) bool {
sLen := len(s)
tLen := len(t)
if sLen != tLen {
return false
}
byteCount := make([]int, 26)
for i := range sLen {
num := int(s[i] - 'a')
byteCount[num]++
}
for j := range tLen {
num := int(t[j] - 'a')
if byteCount[num] == 0 {
return false
}
byteCount[num]--
}
return true
}
この解答は、より高速かつメモリ効率が良いです。
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(1)
- 使われる文字が英小文字（最大26種類）に限られており、O(1)とみなせる
参考
今回の問題と似ている問題も以下の記事で紹介していますので、参考にしてください。
Discussion