Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 221 B問題 typo

AtCoder ABC ABC221 B問題 200 pts

問題

提出解答

問題の概要

2 つの文字列 $S,T$ は以下の操作を高々1回行うことで一致させられるか?

$S$ の隣り合う2つの文字を入れ替える.

制約

$S,T$ は英小文字列
$2 \leq |S|=|T| \leq 100$

解法

$|S|$ に高々1回の操作を施して一致させることができる文字列は

$S$ 自身
$S$ の1文字目と2文字目を入れ替えた文字列 $S_{1,2}$
$S$ の2文字目と3文字目を入れ替えた文字列 $S_{2,3}$
$\vdots$
$S$ の $|S|-1$ 文字目と $|S|$ 文字目を入れ替えた文字列 $S_{|S|-1,|S|}$

の高々 $|S|+1$ 個である. $|S| \leq 100$ という制約から, $S, S_{1,2}, S_{2,3}, \dots, S_{|S|-1,|S|}$ がそれぞれ $T$ と一致するかどうかを判定し, 1つでも一致すれば Yes, 1つも一致しなければ No である. 愚直な判定方法でも $O(|S||T|)=O(|S|^2)$ で判定できる.