JavaScriptで山括弧（<>）の文字列をバランスさせる関数の実装方法

山括弧（< と >）だけで構成された文字列が与えられ、すべての括弧が正しく対応するように、文字列の先頭と末尾に必要な括弧を追加する関数を作成する問題を考えてみましょう。

山括弧のマッチ条件とは

山括弧がマッチしている状態とは、すべての < に対して対応する > が存在し、すべての > に対して対応する < が存在することを指します。

たとえば、入力文字列が次の場合：

const str = '><<><';

期待される出力

const output = '<><<><>>';

この例では、文字列をバランスさせるために、先頭に < を1つ、末尾に >> を2つ追加しています。

解決のアプローチ

この問題は、カウンターを使ったシンプルなアルゴリズムで解決できます。手順は以下の通りです。

• これまでに出現した未対応の開きタグ < の数をカウントする変数を用意します。
• 文字列を走査中に > に遭遇し、かつ現在有効な開きタグが存在しない場合、その > に対応する < を先頭に追加する必要があるため、その数をカウントします。
• 走査が終わった時点で残っている開きタグの数と同じ数だけ、末尾に > を追加します。

実装コード

実際のコードは以下のようになります。

const str = '><<><';
const buildPair = (str = '') => {
    let count = 0;   // 未対応の開きタグの数
    let extras = 0;  // 先頭に追加が必要な '<' の数
    for (const char of str) {
        if (char === '>') {
            if (count === 0) {
                extras++;
            } else {
                count--;
            }
        } else {
            count++;
        }
    }
    const leadingTags = '<'.repeat(extras);
    const trailingTags = '>'.repeat(count);
    return leadingTags + str + trailingTags;
};
console.log(buildPair(str));

実行結果

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

><<><>>

処理のポイント

このアルゴリズムでは、文字列を一度走査するだけで済むため、計算量は O(n)、空間計算量も結果の構築に必要な分のみで O(n) となります。String.prototype.repeat() メソッドを使うことで、必要な数の括弧を簡潔に生成できる点もポイントです。