LeetCode 383. Ransom Note
はじめに
LeetCode 「383. Ransom Note」の問題をGoで解きました。
問題
問題文
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.
和訳
2つの文字列 ransomNote と magazine が与えられた場合、magazine の文字を使って ransomNote を作成できる場合は true を、そうでない場合は false を返します。
magazine の各文字は、ransomNote では一度しか使用できません。
例
Input: ransomNote = "a", magazine = "b"
Output: false
Input: ransomNote = "aa", magazine = "ab"
Output: false
Input: ransomNote = "aa", magazine = "aab"
Output: true
制約
- 1 <= ransomNote.length, magazine.length <= 105
- ransomNote and magazine consist of lowercase English letters.
解答1
ransomNote の各文字が magazine に「十分な数」含まれていれば true を返す、という問題です。
まず以下のような実装を考えました。
byteをキー、intをバリューとして持つマップを作ります。
そこにmagazineの各文字の出現回数を記録し、ransomNoteを捜査しながら文字が出現したらバリューを引きます。
マップのキーは存在しない、あるいはバリューが0以下になったらfalseと判定します。
コード
func canConstruct(ransomNote string, magazine string) bool {
rnLen := len(ransomNote)
mzLen := len(magazine)
charMap := make(map[byte]int)
for i := range mzLen {
charMap[magazine[i]]++
}
for i := range rnLen {
val, ok := charMap[ransomNote[i]]
if ok == false || val <= 0 {
return false
}
charMap[ransomNote[i]]--
}
return true
}
補足
for i := range mzLenという書き方は、go1.22 から可能です。
それ以前の場合は、for i := 0; i < mzLen; i++という形で記述する必要があります。
計算量
- 時間的計算量：O(m + n)
- 空間的計算量：O(1)
解答2
解答1は map[byte]intを作りましたが、固定長配列 [26]int を使うことで省メモリで効率の良い実装が可能です。
コード
func canConstruct(ransomNote string, magazine string) bool {
charCounts := make([]int, 26) // 'a'〜'z'
for i := 0; i < len(magazine); i++ {
charCounts[magazine[i]-'a']++
}
for i := 0; i < len(ransomNote); i++ {
charCounts[ransomNote[i]-'a']--
if charCounts[ransomNote[i]-'a'] < 0 {
return false
}
}
return true
}
charCounts[0] は a の出現回数、charCounts[1] は b の出現回数...といった形となり、
インデックス = 対応する文字として扱っています。
magazine[i] - 'a' の部分で文字を0~25に変換しています。
これは文字 'a' のASCII値（97）を引いているので、たとえば 'c'（99）は 99 - 97 = 2 となります。
2つ目のfor文では、該当するインデックスの値から1を引き、マイナスになった時点でfalseと判定できます。
計算量
- 時間的計算量：O(m + n)
- 空間的計算量：O(1)
Discussion