JavaScriptで部分列の組み合わせから文字列を作れるか判定する方法

問題の概要

JavaScriptで、2つの文字列(第一引数をstr1、第二引数をstr2と呼びます)を受け取る関数を書くことを考えてみましょう。この関数の目的は、str1の中に部分列(subsequence)としてstr2が含まれているかどうかを判定することです。

ここでいう部分列とは、元の文字列からいくつかの文字をスキップすることは許されるが、選び出した文字同士の並び順は維持しなければならないというルールのもとで組み合わせた文字列のことです。

具体例

たとえば、入力として次のような文字列が与えられたとします。

const str1 = 'desxooajmepwele';
const str2 = 'example';

このときの出力は次のようになります。

const output = true;

これは、「example」という文字列が、str1から一部の文字を選び出し、その順序を保ったまま組み合わせることで構築できるためです。

実装コード

この判定処理を実現するコードは以下の通りです。

const str1 = 'desxooajmepwele';
const str2 = 'example';
const containsString = (str1 = '', str2 = '') => {
    let [foundAt, next] = [0, 0];
    for(const char of str2){
        next = str1.slice(foundAt).indexOf(char);
        if (next === - 1){
            return false;
        };
        foundAt += next + 1;
    };
    return true;
};
console.log(containsString(str1, str2));

実行結果

コンソールには次のように表示されます。

true

コードの解説

このアルゴリズムの仕組みを簡単に整理してみましょう。

• foundAt: 次に探索を開始するstr1内の位置(インデックス)を記録する変数です。
• next: 現在注目しているstr2の文字が、str1の残りの範囲のどこに存在するかを示すインデックスです。
• str2の各文字について順番に、str1の未探索領域(slice(foundAt))の中から該当する文字を検索します。
• 文字が見つからなかった場合(indexOfが-1を返した場合)は、その時点でfalseを返して処理を終了します。
• 見つかった場合は、foundAtを見つけた位置の次まで進めます。これにより、以降の文字は必ずそれより後ろから探されることになり、文字の順序が維持されることが保証されます。
• str2のすべての文字が見つかれば、最終的にtrueを返します。

このアプローチでは、再帰処理やバックトラックが不要で、追加のメモリ消費もほとんどありません。最悪でもO(len1 × len2)程度の計算量に収まるため、シンプルながら実用性の高い部分列判定の実装と言えます。