土下座しながら探索中

主に競技プログラミング

AOJ 1227 : 77377

問題リンク:77377 | Aizu Online Judge

問題概要;
n(1<= n <= 100)のワードからなる辞書と1から9までの数字からなる文字列が与えられる。文字列を適当にくぎり辞書のワードを指定された条件のもとで適しているものを割り当てた際に考えられる文字列をすべて表示せよ。(出力の順番は関係ない)

使用した言語:C++

解法;
ワードを数字に変換し、DFSを行う。
例えば press -> 77377
    the -> 843

数字に変換したら再帰関数で文字列の先頭から数字化したワードの長さ分をみてマッチしていればその長さ分先頭から文字列を削除した文字列をもって再帰
最終的に文字列の長さが0になったらできあがった文章を保存して終了。

コード:

int letters[] = {2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9};
vector<string> result;
map<string,string> dictionary;      

string make_intWord(string word)
{
  stringstream ss;
  rep(i,word.size())
    {
      ss << letters[word[i]-'a'];
    }
  return ss.str();
}

void rec(string sequence,string message)
{
 
  for(map<string,string>::iterator it = dictionary.begin();it != dictionary.end();it++)
    {
      if(sequence.size() < (*it).S.size())
	continue;

      if(sequence.substr(0,(*it).S.size()) == (*it).S)
	{
	  if(sequence.size() == (*it).S.size())
	    {
	      result.pb(message + " " + (*it).F);
	      continue;
	    }
	  rec(sequence.substr((*it).S.size(),sequence.size()-(*it).S.size() ),message+ " " +(*it).F );
	}
    }  
 

}

int main()
{

  int n;
  while(true)
    {
      cin >> n;
      if(!n)break;

      result.clear();
      dictionary.clear();
      
      rep(i,n)
	{
	  string word;
	  cin >> word;
	  dictionary[word] = make_intWord(word);
	  //cout << "word : " << word << " -> " << dictionary[word] << endl;
	}

      string sequence;
      cin >> sequence;

      rec(sequence,"");

      rep(i,result.size())
	{
	  cout << result[i].substr(1,result[i].size()-1) << "." <<  endl;
	}
      cout << "--" << endl;
    }
  return 0;
}