程序员面试金典 – 面试题 17.13. 恢复空格（DP+Trie树）网络Michael是个半路程序员-

1. 题目

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。
像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboot"。
在处理标点符号和大小写之前，你得先把它断成词语。
当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。
假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。

注意：本题相对原题稍作改动，只需返回未识别的字符数

示例： 输入： dictionary = ["looked","just","like","her","brother"] sentence = "jesslookedjustliketimherbrother" 输出： 7 解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。（jess tim）  提示： 0 <= len(sentence) <= 1000 dictionary中总字符数不超过 150000。 你可以认为dictionary和sentence中只包含小写字母。 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/re-space-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 动态规划

• dp[i] 表示包含 i 字符结尾的字符串 最少的未识别字符数，初始为 i+1（全部未识别）
• 将 [ 0, i ] 区间切分，[ 0, j-1 ]，[ j, i ] ，遍历所有的 j （j <= i）
• 如果字典包含字符串 [ j, i ]，
  $dp[i] = min(dp[i], dp[j-1])$

  dp[i]=min(dp[i],dp[j−1])

• 如果字典不包含字符串 [ j, i ]，
  $dp[i] = min(dp[i], dp[j-1]+i-j+1)$

  dp[i]=min(dp[i],dp[j−1]+i−j+1)

• 一旦 dp[i] == 0，可以终止内层循环

class Solution { public: int respace(vector<string>& dictionary, string sentence) { if(sentence.empty()) return 0; int i, j, n = sentence.size();         unordered_set<string> s;         vector<int> dp(n,INT_MAX); for(auto& d : dictionary)       s.insert(d); for(i = 0; i < n; ++i) {             dp[i] = i+1; if(s.count(sentence.substr(0,i+1))) {                 dp[i] = 0; continue; } for(j = i; j > 0; --j) { if(s.count(sentence.substr(j,i-j+1)))                     dp[i] = min(dp[i], dp[j-1]); else                     dp[i] = min(dp[i], dp[j-1]+i-j+1); if(dp[i]==0) break; } } return dp[n-1]; } }; 

1156 ms 446.1 MB

2.2 Trie树

• 在上面的思路下，将字典字符串反向插入trie树
• 内层循环可以改为向前在trie树中查找存在的字符串最大长度，一旦不存在某个字符就不必再往前遍历了，因为肯定不存在，可以提高效率。

class trie { public:  trie* cur;  trie* next[26] = {NULL}; bool isEnd = false; void insert(string& s) {   cur = this; for(int i = s.size()-1; i >= 0; --i)//反向插入 { if(cur->next[s[i]-'a'] == NULL) {     cur->next[s[i]-'a'] = new trie(); }    cur = cur->next[s[i]-'a']; }   cur->isEnd = true; } }; class Solution { public: int respace(vector<string>& dictionary, string sentence) { if(sentence.empty()) return 0; int i, j, n = sentence.size();         unordered_set<string> s;      trie *t = new trie(), *cur; for(auto& d : dictionary)       t->insert(d);//字典插入trie树         vector<int> dp(n,INT_MAX); for(i = 0; i < n; ++i) {             dp[i] = i+1;             cur = t; for(j = i; j >= 0; --j)//从i处向前在trie树中查找单词 { if(cur->next[sentence[j]-'a'])//下一个字符存在 { if(cur->next[sentence[j]-'a']->isEnd)//且是结束位置 { if(j > 0)                       dp[i] = min(dp[i], dp[j-1]); else                       dp[i] = 0; } else//不是结束位置，不匹配 { if(j > 0)                       dp[i] = min(dp[i], dp[j-1]+i-j+1); else                       dp[i] = min(dp[i], i-j+1); } } else//下一个字符不存在，可以结束了 { if(j > 0)                      dp[i] = min(dp[i], dp[j-1]+i-j+1); else                         dp[i] = min(dp[i], i-j+1); break; } if(dp[i]==0) break;                 cur = cur->next[sentence[j]-'a']; } } return dp[n-1]; } }; 

120 ms 153.8 MB