JavaScriptで最大1文字の削除により回文を形成できるか判定する方法

問題概要

今回求められているのは、文字列 str を第一引数（唯一の引数）として受け取る JavaScript 関数を作成することです。

この関数では、文字列から 最大1文字 を削除することが許されており、その操作によって文字列を回文にできるかどうかを判定する必要があります。回文とは、前から読んでも後ろから読んでも同じになる文字列のことです。なお、そもそも1文字も削除しなくてよいケースも含まれます。

入出力の例

たとえば、関数への入力が以下の場合を考えてみましょう。

入力

const str = 'dr.awkward';

出力

const output = true;

出力の解説

文字列から「.」を1文字削除すると「drawkward」になり、これは前から読んでも後ろから読んでも同じ文字列となるため、結果は true になります。

アルゴリズムの考え方

この問題は、文字列の両端から中央へ向かって文字を比較していく「二重ポインタ（ツーポインタ）」という手法で効率的に解くことができます。

1. 文字列の左端と右端から順番に、対応する位置の文字同士を比較していきます。
2. すべて一致すれば、その時点ですでに回文であるため true を返します。
3. 不一致が見つかった場合は、左側の文字をスキップした場合と右側の文字をスキップした場合のどちらか一方で、残りの部分が回文になるかを確認します。どちらかが成立すれば true、どちらも成立しなければ false を返します。

コード例

以下が実際のコードです。

const str = 'dr.awkward';
const validPalindrome = (str = '') => {
    const valid = (left, right) => {
        for (let i = left; i <= Math.floor((left + right) / 2); i++) {
            if (str[i] !== str[right - (i - left)]) {
                return false
            }
        }
        return true
    }
    for (let i = 0; i <= Math.floor(str.length / 2); i++) {
        const right = str.length - 1 - i
        if (str[i] !== str[right]) {
            return valid(i, right - 1) || valid(i + 1, right)
        }
    }
    return true
}
console.log(validPalindrome(str));

コードの解説

内部で定義されているヘルパー関数 valid(left, right) は、指定された範囲 [left, right] 内の文字列が回文になっているかどうかを判定する役割を担っています。範囲内の文字を両端から中央に向かって比較し、一箇所でも不一致があれば false を返します。

メインのループでは、文字列長の半分まで左右の対応する文字を比較していきます。不一致が見つかった時点で、「左側の文字を削除するパターン」と「右側の文字を削除するパターン」のいずれかが成立するかを || 演算子で判定しています。これにより、削除できる文字は1文字だけという条件を正しく守りながらチェックを行えます。

ループが最後まで完了して不一致が一度も見つからなければ、元の文字列自体がすでに回文であるため true が返されます。

このアルゴリズムの計算量は O(n)、空間計算量は O(1) であり、文字列を実際に削除・生成せずに済む点が大きな特徴です。

実行結果

true