问题分析

我们需要根据给定的数字序列（由$2$到$9$的数字组成）和字典中的单词，找出所有可能的单词组合，使得这些单词的字母对应的数字序列拼接起来正好等于输入的数字序列。输出结果需要按字典序排列。

解决思路

1. 数字到字母的映射： • 建立数字$2$到$9$与字母的映射关系：

   ◦ $2$: $a, b, c$

   ◦ $3$: $d, e, f$

   ◦ $4$: $g, h, i$

   ◦ $5$: $j, k, l$

   ◦ $6$: $m, n, o$

   ◦ $7$: $p, q, r, s$

   ◦ $8$: $t, u, v$

   ◦ $9$: $w, x, y, z$

2. 预处理字典： • 将字典中的每个单词转换为对应的数字序列。例如，单词$press$转换为$77377$。

   • 使用字典树（Trie）存储这些数字序列，以便快速查找匹配的前缀。

3. 回溯法匹配： • 从数字序列的开头开始，尝试匹配字典中的单词：

   ◦ 对于当前数字序列的前缀，查找所有可能的单词匹配。

   ◦ 如果找到匹配的单词，递归处理剩余的数字序列。

   ◦ 使用回溯法探索所有可能的匹配组合。

4. 结果排序： • 收集所有可能的单词组合后，按字典序排序输出。

代码实现

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

string to_seq(string word)
{
  for (string::iterator it = word.begin(); it != word.end(); ++it) {
    switch (*it) {
      case 'a' ... 'c': *it = '2'; break;
      case 'd' ... 'f': *it = '3'; break;
      case 'g' ... 'i': *it = '4'; break;
      case 'j' ... 'l': *it = '5'; break;
      case 'm' ... 'o': *it = '6'; break;
      case 'p' ... 's': *it = '7'; break;
      case 't' ... 'v': *it = '8'; break;
      case 'w' ... 'z': *it = '9'; break;
    }
  }
  return word;
}

void dfs(const vector<pair<string,string> >& dic, const string& seq, vector<string>& ans, const string& word = "")
{
  if (seq.empty()) {
    ans.push_back(word);
  } else {
    for (vector<pair<string,string> >::const_iterator it = dic.begin(); it != dic.end(); ++it) {
      if (seq.size() >= it->second.size() && seq.find(it->second) == 0) {
        dfs(dic, seq.substr(it->second.size()), ans, word + it->first + " ");
      }
    }
  }
}

struct format
{
  void operator()(string& w) const { w[w.size()-1] = '.'; }
};

int main()
{
  int N;
  ostream_iterator<string> oiter(cout, "\n");
  while (cin >> N && N != 0) {
    vector<pair<string,string> > dic(N);
    for (int i = 0; i < N; i++) {
      cin >> dic[i].first;
      dic[i].second = to_seq(dic[i].first);
    }
    string seq;
    cin >> seq;
    vector<string> ans;
    dfs(dic, seq, ans);
    sort(ans.begin(), ans.end());
    for_each(ans.begin(), ans.end(), format());
    copy(ans.begin(), ans.end(), oiter);
    *oiter++ = "--";
  }
  return 0;
}