把电话号码转换成为词典中可以记忆的的单词的组合，找到最短的组合。

我这道题应用到的知识点：

1 Trie数据结构

2 map的应用

3 动态规划法Word Break的知识

4 递归剪枝法

思路：

1 建立Trie字典树，方便查找， 但是字典树不是使用字符来建立的，而是把字符转换成数字，建立一个数字字典树， 然后叶子节点设置一个容器vector 装原单词。

2 动态规划建立一个表，记录可以在字典树中找到的字符串的前缀子串

3 如果找到整个串都在字典树中，那么就可以直接返回这个单词。如果无法直接找到，那么就要在表中找到一个前缀子串，然后后面部分在字典树中查找，看是否找到包含这个子串的单词，并且要求找到的单词长度最短。- 这里可以使用剪枝法提高效率。

原题：http://acm.timus.ru/problem.aspx?space=1&num=1002

作者：靖心 - http://blog.csdn.net/kenden23

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; class PhoneNumber1002_2 { static const int SIZE = 10; struct Node { vector
        
          words; Node *children[SIZE]; explicit Node () : words() { for (int i = 0; i < SIZE; i++) { children[i] = NULL; } } }; struct Trie { Node *emRoot; int count; explicit Trie(int c = 0) : count(c) { emRoot = new Node; } ~Trie() { deleteTrie(emRoot); } void deleteTrie(Node *root) { if (root) { for (int i = 0; i < SIZE; i++) { deleteTrie(root->children[i]); } delete root; root = NULL; } } }; void insert(Trie *trie, string &keys, string &keyWords) { int len = (int)keys.size(); Node *pCrawl = trie->emRoot; trie->count++; for (int i = 0; i < len; i++) { int k = keys[i] - '0'; if (!pCrawl->children[k]) { pCrawl->children[k] = new Node; } pCrawl = pCrawl->children[k]; } pCrawl->words.push_back(keyWords); } Node *search(Node *root, string &keys) { int len = (int)keys.size(); Node *pCrawl = root; for (int i = 0; i < len; i++) { int k = keys[i] - '0'; if (!pCrawl->children[k]) { return NULL;//没走完所有keys } pCrawl = pCrawl->children[k]; } return pCrawl; } void searchLeft(Node *leaf, Node *r, int len, int &prun) { if (len >= prun) return; if (leaf->words.size()) { r = leaf; prun = len; return; } for (int i = 0; i < SIZE; i++) { searchLeft(leaf->children[i], r, len+1, prun); } } void wordsToKey(string &keys, string &keyWords, unordered_map
         
           &umCC) { for (int i = 0; i < (int)keyWords.size(); i++) { keys.push_back(umCC[keyWords[i]]); } } void charsToMap(const string phdig[], unordered_map
          
            &umCC) { for (int i = 0; i < 10; i++) { for (int k = 0; k < (int)phdig[i].size(); k++) { umCC[phdig[i][k]] = i + '0'; } } } string searchComb(Trie *trie, string &num) { vector
           
             tbl(num.size()); for (int i = 0; i < (int)num.size(); i++) { string s = num.substr(0, i+1); Node *n = search(trie->emRoot, s); if (n && n->words.size()) { tbl[i].append(n->words[0]); continue;//这里错误写成break！！ } for (int j = 1; j <= i; j++) { if (tbl[j-1].size()) { s = num.substr(j, i-j+1); n = search(trie->emRoot, s); if (n && n->words.size()) { tbl[i].append(tbl[j-1]); tbl[i].append(" "); tbl[i].append(n->words[0]); break; } } } } if (tbl.back().size()) { return tbl.back(); } string ans; for (int i = 0; i < (int)tbl.size() - 1; i++) { if (tbl[i].size()) { string tmp = tbl[i]; string keys = num.substr(i+1); Node *n = search(trie->emRoot, keys); if (!n) continue; Node *r = NULL; int prun = INT_MAX; searchLeft(n, r, 0, prun); tmp += r->words[0]; if (ans.empty() || tmp.size() < ans.size()) { ans = tmp; } } } return ans.empty()? "No solution." : ans; } //测试函数，不使用解题 void printTrie(Node *n) { if (n) { for (int i = 0; i < SIZE; i++) { printTrie(n->children[i]); for (int j = 0; j < (int)n->words.size(); j++) { cout<
            
             words[j]<
             
               umCC; charsToMap(phdig, umCC); int N; string num, keys, keyWords; while ((cin>>num) && "-1" != num) { cin>>N; Trie trie; while (N--) { cin>>keyWords; wordsToKey(keys, keyWords, umCC); insert(&trie, keys, keyWords); keys.clear();//别忘记清空 } cout<