AtCoderのABC007_2問題で登場する辞書式順序（Lexicographical Order）の定義について混乱する方がいます。特に文字列”aaa”と”aab”の比較における条件Si < Sjの理解が難しいケースです。この記事では、辞書式順序の原理と具体例を交えて解説します。
辞書式順序とは何か
辞書式順序とは、文字列をアルファベット順に並べる方法です。左から順に各文字を比較し、最初に異なる文字が現れた位置で大小を判定します。
例えば”abc”と”abd”を比較する場合、最初の文字’a’は同じ、2文字目’b’も同じ、3文字目で’c’ < ‘d’となるため”abc” < “abd”と判定されます。
“aaa”と”aab”の比較例
文字列”aaa”と”aab”を比較する際、左から順に文字を比較します。1文字目’a’ = ‘a’、2文字目’a’ = ‘a’、3文字目’a’ < ‘b’となるため、”aaa” < “aab”となります。
この例から分かる通り、i=2,j=1の比較は誤解です。比較は同じ位置の文字同士で行うため、3文字目で初めて大小が決まります。
辞書式順序のポイント
重要なポイントは以下です。
- 文字列は左から順に比較する
- 最初に異なる文字が現れた位置で大小が決まる
- 異なる長さの文字列の場合、共通部分が同じなら短い方が先
具体例の応用
さらに例を示します。”abc” < “abcd”となります。共通部分”abc”が同じなので、短い文字列”abc”が先になります。
このルールを理解すれば、AtCoderなどの問題で文字列のソートや比較を正しく実装できます。
まとめ
“aaa”と”aab”の比較でi=2,j=1のような誤解は生じやすいですが、辞書式順序は文字の位置ごとに比較する原理に従います。最初に異なる文字が現れた位置で大小が決まるため、”aaa” < “aab”は正しい判定です。
この理解をもとに、AtCoderのABC007_2問題や類似の文字列比較問題に対応できるようになります。
コメント