SRM468 Div1 Easy(250), Div2 Medium(500) T9

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;
}