JavaScriptで各文字を隣接する文字に変更して回文を作成できるか判定する

問題

文字列を引数として受け取り、以下の操作を行えるJavaScript関数を作成することを求められています。

• 各文字は、必ずアルファベット上で1つ前または1つ後ろの文字に変更しなければなりません。
• 「a」は「b」のみに、「z」は「y」のみに変更できます。

これらの操作を適用した結果のうち、少なくとも1つが回文になれば true を、そうでなければ false を返す関数を実装してください。

考え方

回文になるためには、文字列の先頭から i 番目の文字と、末尾から i 番目の文字が一致している必要があります。しかし今回は各文字を ±1 の範囲でしか変更できないため、単純な一致判定では不十分です。

そこで、対応する2つの文字のコードポイント（文字コード）の絶対差に注目します。

• 差が 0 の場合： 2つの文字を同じ方向（両方とも +1、または両方とも −1）へ変更すれば一致します。
• 差が 2 の場合： 小さい方の文字を +1、大きい方の文字を −1 へ変更すれば、同じ文字で一致します。
• 差が 1 の場合： 各文字は ±1 しか動けないため、どのように変更しても一致させることはできません。

以上より、先頭から中央まで走査し、対応する文字ペアの絶対差が 0 または 2 以外であれば false を返し、すべてのペアが条件を満たしていれば true を返すことで判定できます。

コード例

const str = 'adfa';
const canFormPalindrome = (str = '') => {
    const middle = str.length / 2;
    for(let i = 0; i < middle; i++){
        const first = str[i].charCodeAt();
        const last = str[str.length - (i + 1)].charCodeAt();
        const distance = Math.abs(last - first);
        if(distance > 2 || distance === 1){
            return false;
        }
    }
    return true;
};
console.log(canFormPalindrome(str));

実行結果

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

true

この例では、文字列 'adfa' に対して判定を行っています。対応する文字ペア（a と a、d と f）の差を確認すると、最初のペアは差 0、次のペア（d=100、f=102）は差 2 であり、いずれも条件を満たすため、適切な操作によって回文を作成できることが分かります。

計算量

文字列の半分だけ走査すればよいため、時間計算量は O(n)、追加のメモリ使用量は O(1) という効率的なアルゴリズムになっています。