##はじめに
ABC049C - 白昼夢を検索文字列の特性上、文字列をリバースして導く方法で解きました。
解きかたは模範解答とされている手法なのでさておき、
こちらをGoで実現しようとしたとき検索能力の低さゆえ、Goに以下の機能が見つけられず手作りとなってしまったので、改良したいと思いメモです。
- 文字列のリバース
- 開始〜終了桁数を指定した文字列の抜き出し(例:abcを1文字目から2文字目で抜き出して「b」を求める)
##提出コード
package main
import (
"fmt"
)
func main() {
var s string
annwer := "YES"
divide := [4]string{"dream", "dreamer", "erase", "eraser"}
fmt.Scanf("%s", &s)
// リバース
for i :=0; i < len(divide); i++ {
divide[i] = getReverse(divide[i])
}
reverse := getReverse(s)
// 後ろから一致するものを抜き出す
j := 0 // 開始位置
for j < len(reverse) {
annwer = "NO"
for i := 0; i < 4; i++ {
// 比較する文字列を必要な範囲で抜き出す
var str string
for k := j; k < j + len(divide[i]); k++ {
if k >= len(reverse) {
continue
}
str += string(reverse[k])
}
// 比較
if str == divide[i] {
// 一致した分開始位置をずらす
j += len(divide[i])
annwer = "YES"
break
}
}
// ここにNOで来た時点でアウトなので終わり
if annwer == "NO" {
break
}
}
fmt.Println(annwer)
}
func getReverse(s string) string {
rs := []rune(s) // 今回マルチバイト文字ではないが想定してrune
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
rs[i], rs[j] = rs[j], rs[i]
}
return string(rs)
}
コード長:1263 Byte
実行時間:174 ms
メモリ:3912 KB
##その他1(追記)
コメントでアドバイスいただいた正規表現にて実現した場合、とてもスッキリしています。
アルゴリズム理解のため、パッケージはあまり使いたくない気持ちでAtCorderをやっていますが、このスッキリ感には負ける…。
package main
import (
"fmt"
"regexp"
)
func main() {
var s string
divide := `^(dream|dreamer|erase|eraser)*$`
fmt.Scanf("%s", &s)
if regexp.MustCompile(divide).Match([]byte(s)) {
fmt.Println("YES")
} else {
fmt.Println("NO")
}
}
コード長:279 Byte
実行時間: 164 ms
メモリ:2820 KB
##その他2
stringsパッケージのReplaceで一致したら""と置換してしまい、最後0文字になったらYESという方法
※AtCorderの白昼夢で検索するとよくヒットしますので割愛。
##おわりに
提出コードを書いたときは、冗長すぎておかしくなりそうでした。
正規表現のアドバイスをくださった@superrino130さん、ありがとうございました!!
以下は引き続き捜索中です。あまりニッチではないパッケージで実現可能でしたら教えていただけると嬉しいです。
- 文字列のリバース
- 開始〜終了桁数を指定した文字列の抜き出し(例:abcを1文字目から2文字目で抜き出して「b」を求める)