ABC349C Golang 回答メモ

概要

この記事ではAtCoder Beginner Contest 349 のC問題の解答を自分用にメモしたものです

公式の回答はこちらからご覧ください

問題はこちら

問題の前提

入力される文字列S に対して、文字列Tが、条件に合致していればtrue, そうでなければfalse を返却します。
空港コードという言葉が出てきますが、実在するかどうかは関係ないため、厳密に空港コードであるかどうかは考えなくて良いです。

満たすべき条件は下記の2つ

• S の長さ3の（連続とは限らない）部分列をとり、それを英大文字に変換したものを T とする
• S の長さ2の（連続とは限らない）部分列をとり、それを英大文字に変換したものの末尾に X を追加したものを T とする

また、問題に書いてありますが、解答するに当たって 「部分列」 という知識が前提となります。

部分列の定義は下記です。

{An}を数列とする。この時、項一部を取り出し、順番を変えずに並べた数列を部分列(subsequence)という
引用元: 数学の景色

この問題キモは部分列の「順番を変えずに並べた」という部分にあります。

文字列Tの文字が、文字列Sに含まれていることだけを判定すれば良いわけではなく、文字列Tの1文字目が見つかった場合、2文字目は 1文字目のindex よりも後ろ から見つけるようにしなければいけません。

例で示します。
下記のように文字列S, T がそれぞれ"a","b","c" の文字で構成されていたとします。

s = "cab"
t = "ABC"

文字列Tに含まれる3文字が文字列Sのどのindex で登場しているかを整理しましょう。

状況を整理すると、
"A" はindex=1 で登場
"B" はindex=2 で登場
"C" はindex=0 で登場
となります。

部分列の定義では、「対象の配列に対して、一部を取り出し順番を変えずに並べた」配列が部分列と呼ばれます。
今回の問題に当てはめると、TはSの部分列であるため、Sの文字列の一部を取り出し、順番を変えずに並べている必要があります。

これをふまえると、Tの最後に登場する文字"C"は、Sの先頭に登場しているため、文字列Tは文字列Sの部分列ではない ということになります。

問題の例題ではこの条件を見逃しても大丈夫な文字列が与えられているので、部分列の定義を知らなかった自分はうまく正解を出せませんでした。

これらを踏まえてGo言語で実装します。

実装

package main

import (
	"fmt"
	"strings"
)

func getInput() (string, string) {

	var s string
	var t string
	fmt.Scan(&s)
	fmt.Scan(&t)

	return s, t
}

func main() {
	s, t := getInput()

	if isAirportCode(s, t) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

func isAirportCode(s, t string) bool {
	// 末尾にxを追加することでTにXが入る場合に対応させる
	s = s + "x"

	t = strings.ToLower(t)
	idx := 0
	for _, r := range t {
		// 部分列の条件に当てはめるために、idx 以降の文字列を取得する
		index := strings.Index(s[idx:], string(r))
		
		// 見つからないならその時点でfalse 
		if index == -1 {
			return false
		}
		// 見つかった場合、次のループでsから取り出す場所を更新
		// そのまま更新すると、今見つけた文字も含めた文字列を抜き出してしまうので、+1する
        idx += index+1
	}
	// 3文字全て見つかったらOK
	return true
}

各所にコメントを入れていますが、キモになるのは「順番をそのままにして並べる」ことです。
idx を更新することで、Tの持つ文字が見つかったなら、それより後ろの文字列から探す。を実現しています。

idx の更新方法には少し癖があるかもしれませんが、よりわかりやすい方法があればコメントいただけると嬉しいです。