回文作れるか判定

問題

文字列から回文が作れるか判定する

考え方

文字の数を数えて、文字の種類Mに対して、M-1個の文字が偶数回出れば良い。 アクセスを早くするためにhashを利用する。

計算量

文字列の長さをN、文字の種類をMとする。N >= M である。

hashに記録する際にはO(N)、偶数か判定する際にO(M)。 よって、時間計算量はO(N)。

記録するのはhash tableだけなので、空間計算量はO(M)

コード例

C++

#include<stdio.h>
#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;

bool kaibun(std::string str){
    // hashに記録
    int i, n;
    string s;
    unordered_map<std::string, int> hash;
    for(i=0; i<str.length(); i++){
        s = str.substr(i, 1);
        if(hash[s] == false){
            hash[s] = 1;
        }else{
            hash[s] += 1;
        }
    }
    unordered_map<std::string, int>::iterator iter;
    n = 0;
    for(iter=hash.begin(); iter!=hash.end(); iter++){
        //偶数か判定
        if(iter->second%2==0){
            n++;
        }
        cout << iter->first<< " " << iter->second << endl;
    }
    if(n >= hash.size()-1){
        return true;
    }else{
        return false;
    }
}

int main(void){

    std::string str;
    bool flg;
    str = "acdefadefaagg";
    cout << "判定する文字列は " << str <<endl;
    flg = kaibun(str);
    cout << "回文が作れるか? " << boolalpha << flg << endl;
    return 0;
}