JavaScriptでスクランブルされたアルファベット順序に基づいて、配列が辞書式順序でソートされているか確認する方法

文字列の配列を第一引数として受け取るJavaScript関数を作成する必要があります。第二引数には、26個の英小文字アルファベットすべてがランダムな順序で並び替えられた文字列が渡されます。

この関数の役割は、配列内の単語が第二引数で指定された順序に従って辞書式順序(lexicographical order)で正しく並んでいるかどうかを判定することです。正しく並んでいればtrueを、そうでなければfalseを返します。

例

例えば、入力となる単語の配列と順序が以下の場合を考えてみましょう。

const arr = ['this', 'is', 'something', 'mad'];
const order = 'hdetljnopqabcuvwxfgirsykmz';

この場合、出力は以下のようになります。

const output = true;

その理由は、順序文字列の中で「t」が「i」より先に現れ、「i」が「s」より先に現れ、「s」が「m」より先に現れるためです。

実装コード

この問題を解くコードは以下のとおりです。

const arr = ['this', 'is', 'something', 'mad'];
const order = 'hdetljnopqabcuvwxfgirsykmz';
const isPlacedCorrectly = (arr = [], order) => {
    const { length } = arr;
    for(let i = 0; i < length - 1; i++){
       for(let j = 0; j < arr[i].length; j++){
          if(order.indexOf(arr[i][j]) < order.indexOf(arr[i+1][j])) {
            break;
          }
          else if (order.indexOf(arr[i][j]) === order.indexOf(arr[i+1][j])){
            continue;
          } else {
            return false;
          }
       }
    }
    return true;
};
console.log(isPlacedCorrectly(arr, order));

出力結果

コンソールには以下のように出力されます。

true

コードの解説

このコードの動作を順を追って見ていきましょう。

• 外側のループで、配列内の隣接する単語同士を順番に比較します。
• 内側のループで、各単語の文字を先頭から1文字ずつ比較します。
• order.indexOf()を使うことで、各文字がカスタム順序の中で持つ位置(インデックス)を取得できます。
• 前の単語の文字の位置が次の単語の文字の位置より小さい場合、そのペアは正しい順序なので、breakで次の単語ペアの比較に移ります。
• 位置が等しい場合(同じ文字の場合)は、continueで次の文字の比較に進みます。
• 前の単語の文字の位置が大きい場合は順序違反となるため、即座にfalseを返します。

すべての隣接ペアが正しい順序で並んでいれば、最終的にtrueを返します。

計算量について

このアルゴリズムの計算量は、単語の数をN、単語の最大文字数をLとするとO(N × L)になります。各文字の位置の取得にindexOfを使用しているため、内部的には順序文字列(26文字)の走査が発生しますが、長さが固定であるため実用上は問題ありません。さらに高速化したい場合は、事前に各文字の位置をMapやオブジェクトに記録しておき、O(1)で参照できるようにする方法も有効です。