POJ 1409 - 77377

http://poj.org/problem?id=1409

概要

例えば 7 を一度押しただけで p, q, r, s のいずれかが入力されるような携帯電話を考える． 77377 と押すと，可能性のひとつとして "press" という文字列が入力される．

携帯電話に辞書を持たせ，その辞書に存在する単語のみが入力されるようにする．

そのとき，押されたボタンの列に対して入力されうるすべての文字列を出力する．

制約

• 出力は辞書順で
• 入力は特になし？
  • かなり小さいと見ていいっぽい．

解法

DFS するだけ．

 1 #include <iostream>
 2 #include <vector>
 3 #include <iterator>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 string to_seq(string word)
 8 {
 9   for (string::iterator it = word.begin(); it != word.end(); ++it) {
10     switch (*it) {
11       case 'a' ... 'c': *it = '2'; break;
12       case 'd' ... 'f': *it = '3'; break;
13       case 'g' ... 'i': *it = '4'; break;
14       case 'j' ... 'l': *it = '5'; break;
15       case 'm' ... 'o': *it = '6'; break;
16       case 'p' ... 's': *it = '7'; break;
17       case 't' ... 'v': *it = '8'; break;
18       case 'w' ... 'z': *it = '9'; break;
19     }
20   }
21   return word;
22 }
23 
24 void dfs(const vector<pair<string,string> >& dic, const string& seq, vector<string>& ans, const string& word = "")
25 {
26   if (seq.empty()) {
27     ans.push_back(word);
28   } else {
29     for (vector<pair<string,string> >::const_iterator it = dic.begin(); it != dic.end(); ++it) {
30       if (seq.size() >= it->second.size() && seq.find(it->second) == 0) {
31         dfs(dic, seq.substr(it->second.size()), ans, word + it->first + " ");
32       }
33     }
34   }
35 }
36 
37 struct format
38 {
39   void operator()(string& w) const { w[w.size()-1] = '.'; }
40 };
41 
42 int main()
43 {
44   int N;
45   ostream_iterator<string> oiter(cout, "\n");
46   while (cin >> N && N != 0) {
47     vector<pair<string,string> > dic(N);
48     for (int i = 0; i < N; i++) {
49       cin >> dic[i].first;
50       dic[i].second = to_seq(dic[i].first);
51     }
52     string seq;
53     cin >> seq;
54     vector<string> ans;
55     dfs(dic, seq, ans);
56     sort(ans.begin(), ans.end());
57     for_each(ans.begin(), ans.end(), format());
58     copy(ans.begin(), ans.end(), oiter);
59     *oiter++ = "--";
60   }
61   return 0;
62 }