JavaScriptで文字列を並べ替えて回文を作れるか判定する方法

問題の概要

JavaScriptで、文字列を唯一の引数として受け取る関数を作成する必要があります。

この関数の役割は、文字列内の文字を並べ替えることで回文(前から読んでも後ろから読んでも同じになる文字列)を作成できるかどうかを判定することです。回文を作れる場合は true を、作れない場合は false を返します。

例

入力文字列が以下の場合：

const str = 'amadm';

出力は次のようになります：

const output = true;

これは、文字列を並べ替えると「madam」という回文になるためです。

実装コード

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

const str = 'amadm';
const canFormPalindrome = (str = '') => {
    const hash = {};
    let count = 0;
    for (let i = 0; i < str.length; i++) {
        let c = str[i];
        if(c === ' '){
            continue;
        };
        if(hash[c]){
            delete hash[c];
        }else{
            hash[c] = true;
        };
        count++;
    };
    if(count % 2 === 0){
        return Object.keys(hash).length === 0;
    }else{
        return Object.keys(hash).length === 1;
    };
};
console.log(canFormPalindrome(str));

アルゴリズムの解説

このアプローチのポイントは以下のとおりです：

• ハッシュオブジェクトによる管理：各文字が出現するたびにハッシュから削除し、最終的に奇数回出現した文字だけを残します。これにより、出現回数のパリティ(偶奇)を効率的に追跡できます。
• 空白の除外：スペースは判定対象から除外し、実際の文字のみをカウントします。
• 文字数による分岐：文字数が偶数の場合、すべての文字が偶数回出現していれば回文にできます。文字数が奇数の場合、ちょうど1つの文字だけが奇数回出現していれば、その文字を中央に配置して回文を構成できます。

計算量

このアルゴリズムの時間計算量は O(n)(nは文字列の長さ)、空間計算量も O(n) となり、非常に効率的な解法です。

出力

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

true