はじめに
Easy の中でも簡単な問題です。Go は byte や rune が絡むので少し面倒ですが。
文字列 s の中から、最初に 2 回登場したアルファベットを答えなさい、というだけの問題です。
abcabc なら a、abedgdbca なら b です。それだけです。
https://leetcode.com/problems/first-letter-to-appear-twice/submissions/1622046931
1
2
3
4
5
6
7
8
9
10
11
12
|
func repeatedCharacter(s string) byte {
l := make(map[byte]bool, len(s))
ans := byte(0)
for _, c := range []byte(s) {
if _, b := l[c]; b {
ans = c
break
}
l[c] = true
}
return ans
}
|
もう少しシンプルにならないかなぁと Grok 3 に手伝ってもらって簡素化したのが以下です。
1
2
3
4
5
6
7
8
9
10
|
func repeatedCharacter(s string) byte {
seen := make(map[byte]bool)
for _, c := range []byte(s) {
if seen[c] {
return c
}
seen[c] = true
}
return 0
}
|
まあ、AtCoder の探索問題でよく用いられる seen という変数を使ったのと、return を導入したのみです。
面白い解法
bitmask を使った解法がありました。
アルファベットは26種類なので、32bit あればビットをフラグと見立てて過去に現れた文字かどうかを判定できます。
たとえば、abfa という文字をループしたとき、seen 変数のビットマスクは次のように変化します。
1
2
3
4
|
a: 0000 0000 0000 0000 0000 0000 0000 0001
b: 0000 0000 0000 0000 0000 0000 0000 0011
f: 0000 0000 0000 0000 0000 0000 0010 0011
a: ここで return
|
1 << (ch - 'a') の部分で、ビットマスクのどの桁に 1 をセットするかを決め、seen |= bit の部分で実際に 1 をセットしています。論理和ですね。
ちなみにこの解法は、DFSやBFSなどの探索系の問題でよく使われるテクニックですので、頭の片隅に置いておきましょう。
https://leetcode.com/problems/first-letter-to-appear-twice/solutions/2382459/go-bitmask
1
2
3
4
5
6
7
8
9
10
11
12
13
|
func repeatedCharacter(s string) byte {
// Use a bitmask to keep track of whether a character has
// been seen before.
var seen int
for _, ch := range s {
bit := (1 << (ch - 'a'))
if seen&bit > 0 {
return byte(ch)
}
seen |= bit
}
return 0
}
|
翌日 bitmask を使って自力で解いたものです。
bm & n == n は、bm & n > 0 でも OK です。この論理積の結果は 0 or 1 以上だからです。
また、最後の return は、問題文より、文字列中に必ず一度は同じアルファベットが2回登場することが書かれていますので、何を返してもいいです。
ただし、return 文がない場合はエラーとなりますので、return 文は必要です。
1
2
3
4
5
6
7
8
9
10
11
12
|
func repeatedCharacter(s string) byte {
// solution: bitmask
bm := 0
for _, b := range []byte(s) {
n := 1 << (b - 'a')
if bm & n == n {
return b
}
bm |= n
}
return s[0]
}
|