回文作れるか判定
問題
文字列から回文が作れるか判定する
考え方
文字の数を数えて、文字の種類Mに対して、M-1個の文字が偶数回出れば良い。 アクセスを早くするためにhashを利用する。
計算量
文字列の長さをN、文字の種類をMとする。N >= M である。
hashに記録する際にはO(N)、偶数か判定する際にO(M)。 よって、時間計算量はO(N)。
記録するのはhash tableだけなので、空間計算量はO(M)
コード例
#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; }