SRM468 Div1 Easy(250), Div2 Medium(500) T9
辞書のサイズが小さいので、辞書内の単語それぞれについて与えられたキーストロークの数字部分で入力できるか調べる。
#include <string> #include <vector> #include <numeric> #include <algorithm> using namespace std; class T9 { public: string message( vector <string> part, vector <string> dict, vector <string> keystr ); }; string T9::message( vector <string> part, vector <string> dict, vector <string> keystr ) { string key = accumulate( keystr.begin(), keystr.end(), string("") ); int length = (int)key.length(); sort( dict.begin(), dict.end() ); string text; string k = ""; // 各単語の数字部分 int n = 0; // 各単語の#*が表す序数 for ( int i=0; i<length; i++ ) { if ( key[i] == '0' ) text += " "; else if ( key[i] == '#' ) n += 1; else if ( key[i] == '*' ) n += 5; else k += key[i]; // 単語を辞書から探す if ( i == length - 1 || ( key[i] != '0' && key[i+1] == '0' ) ) { int c = 0; for ( int j=0; j<(int)dict.size(); j++ ) if ( dict[j].length() == k.length() ) { bool f = true; for ( int l=0; l<(int)dict[j].length(); l++ ) { int p = k[l] - '1'; if ( find( part[p].begin(), part[p].end(), dict[j][l] ) == part[p].end() ) f = false; } if ( f ) if ( c++ == n ) text += dict[j]; } k = ""; n = 0; } } return text; }