競技プログラミング

ABC303 A – Similar String

https://atcoder.jp/contests/abc303/tasks/abc303_a

イントロダクション

この問題は、2つの文字列が特定の条件を満たすかどうかを判断することが求められています。具体的には、与えられた2つの文字列が「似ている」かどうかを判断する問題です。文字列が「似ている」とは、文字列の各位置の文字が同じか、特定の文字の組み合わせ(’1’と’l’、’0’と’o’)であることを指します。

問題の詳細説明

2つの文字列SとTが与えられます。これらの文字列が「似ている」かどうかを判定する必要があります。

「似ている」文字列とは、次の条件を満たすものを指します:

  • 任意のi(1≤i≤N)について、Sのi番目の文字とTのi番目の文字は「似ている」文字である。

ここで、「似ている」文字とは、次の3つの条件のうち少なくとも1つを満たす文字の組み合わせを指します:

  • xとyは同じ文字
  • xとyの片方が’1’で、もう片方が’l’
  • xとyの片方が’0’で、もう片方が’o’

解答戦略

文字列SとTの各文字を順番に見ていき、「似ている」かどうかを判断します。すべての位置で文字が「似ている」場合には”Yes”を、そうでない場合には”No”を出力します。

具体的な手順は以下の通りです:

  1. 文字列SとTの長さNを取得します。
  2. 文字列SとTを1文字ずつ見ていきます。
  3. 各位置の文字が「似ている」かどうかを判断します。
    • 同じ文字である場合、「似ている」です。
    • Sの文字が’1’でTの文字が’l’、またはその逆の場合、「似ている」です。
    • Sの文字が’0’でTの文字が’o’、またはその逆の場合、「似ている」です。
    • これらの条件を満たさない場合、「似ていない」です。
  4. すべての位置で文字が「似ている」場合には”Yes”を、そうでない場合には”No”を出力します。

コードの解説

以下に問題を解くためのSwiftコードを示します。

let N = Int(readLine()!)!
let S = readLine()!
let T = readLine()!
var isSimilar = true
for i in S.indices {
    let s = S[i]
    let t = T[i]
    if s == t { continue }
    if (s == "1" && t == "l") || (s == "l" && t == "1") { continue }
    if (s == "0" && t == "o") || (s == "o" && t == "0") { continue }
    isSimilar = false
    break
}
print(isSimilar ? "Yes" : "No")

このコードでは、最初に文字列SとTの長さNを取得します。その後、文字列SとTを1文字ずつ調べて、「似ている」かどうかを判断します。すべての文字が「似ている」場合は”Yes”を、そうでない場合は”No”を出力します。

テストケースと実行結果

上記のコードを用いていくつかのテストケースを試してみましょう。

yamlCopy codeInput:
3
l0w
1ow
Output:
Yes
yamlCopy codeInput:
3
abc
arc
Output:
No
yamlCopy codeInput:
4
nok0
n0ko
Output:
Yes

上記の結果から、コードは正しく動作していることが確認できます。

考察と最適化

この問題は、基本的な文字列操作と条件判断を用いて解くことができます。したがって、特に最適化の余地は見られません。

ただし、コードを短くするために、”1″と”l”、”0″と”

“o”の組み合わせをあらかじめセットに保存しておき、それらを用いて比較することも可能です。これにより、コードの見通しをよくすることができます。

また、各文字を比較する際に、「似ている」文字を見つけたらすぐに次の文字に移るようにすることで、処理時間を短縮することも可能です。

ただし、これらの最適化は微々たるものであり、入力サイズが大きくなっても実行時間に大きな影響を与えるものではありません。そのため、特に最適化が必要な場合を除き、上述のコードをそのまま使用して問題を解くことをおすすめします。

結論

以上のように、Swiftを用いて「似た文字列」問題を解決することができました。この問題は、文字列の操作と比較に基づいています。この問題は基本的な文字列操作と、特定の条件に基づいた比較の理解を試す良い問題でした。

なお、解答に関して何か質問や疑問がある場合、または異なる解答方法を知っている場合は、ぜひコメント欄にてお知らせください。あなたのフィードバックは、より良い記事を作成するための重要な参考になります。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です