恢复空格（m)

空格（m)"/>

恢复空格（m)

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"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个未识别字符。
提示：

0 <= len(sentence) <= 1000
dictionary中总字符数不超过 150000。
你可以认为dictionary和sentence中只包含小写字母。

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

字典树 ：

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

3个基本性质：

根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。

C

typedef struct Trie {struct Trie* next[26];bool isEnd;
} Trie;//创建结点
void init(Trie** p) {*p = (Trie*)malloc(sizeof(Trie));(*p)->isEnd = false;memset((*p)->next, NULL, sizeof((*p)->next));
}//连接结点
void insert(Trie* curPos, char* s) {int len = strlen(s);//计算给定字符串的长度 for (int i = len - 1; i >= 0; --i) {int t = s[i] - 'a';if (curPos->next[t] == NULL) {init(&curPos->next[t]);}curPos = curPos->next[t];}curPos->isEnd = true;
}int respace(char** dictionary, int dictionarySize, char* sentence) {int n = strlen(sentence);Trie* root;init(&root);for (int i = 0; i < dictionarySize; i++) {insert(root, dictionary[i]);}int dp[n + 1];memset(dp, 0x3f, sizeof(dp));//把一段内存全部置为无穷大dp[0] = 0;for (int i = 1; i <= n; ++i) {dp[i] = dp[i - 1] + 1;//第一个字母是从1开始Trie* curPos = root;for (int j = i; j >= 1; --j) {int t = sentence[j - 1] - 'a';if (curPos->next[t] == NULL) {break;} else if (curPos->next[t]->isEnd) {dp[i] = fmin(dp[i], dp[j - 1]);//返回两个参数中的较小值，在头文件<math.h>中定义}if (dp[i] == 0) {break;}curPos = curPos->next[t];}}return dp[n];
}

关于0x3f3f3f3f:

0x3f3f3f3f的十进制是1061109567，是10^9级别的（和0x7fffffff一个数量级），而一般场合下的数据都是小于10^9的，所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。 
    另一方面，由于一般的数据都不会大于10^9，所以当我们把无穷大加上一个数据时，它并不会溢出（这就满足了“无穷大加一个有穷的数依然是无穷大”），事实上0x3f3f3f3f+0x3f3f3f3f=2122219134，这非常大但却没有超过32-bit int的表示范围，所以0x3f3f3f3f还满足了我们“无穷大加无穷大还是无穷大”的需求。

最后，0x3f3f3f3f还能给我们带来一个意想不到的额外好处： 
如果我们想要将某个数组清零，我们通常会使用memset(a,0,sizeof(a))，方便又高效，但是当我们想将某个数组全部赋值为无穷大时，就不能使用memset函数而得自己写循环了，因为memset是按字节操作的，它能够对数组清零是因为0的每个字节都是0（一般我们只有赋值为-1和0的时候才使用它）。现在好了，如果我们将无穷大设为0x3f3f3f3f，那么奇迹就发生了，0x3f3f3f3f的每个字节都是0x3f！所以要把一段内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))。

Java

class Solution {public int respace(String[] dictionary, String sentence) {int n = sentence.length();Trie root = new Trie();for (String word: dictionary) {root.insert(word);}int[] dp = new int[n + 1];Arrays.fill(dp, Integer.MAX_VALUE);//java int 类整数的最大值是 2 的 31 次方 - 1 = 2147483648 - 1 = 2147483647//可以用 Integer.MAX_VALUE 表示它，即 int value = Integer.MAX_VALUE;//将MAX_VALUE值分配给指定的dp数组的每个元素dp[0] = 0;for (int i = 1; i <= n; ++i) {dp[i] = dp[i - 1] + 1;Trie curPos = root;for (int j = i; j >= 1; --j) {int t = sentence.charAt(j - 1) - 'a';if (curPos.next[t] == null) {break;} else if (curPos.next[t].isEnd) {dp[i] = Math.min(dp[i], dp[j - 1]);}if (dp[i] == 0) {break;}curPos = curPos.next[t];}}return dp[n];}
}class Trie {public Trie[] next;public boolean isEnd;public Trie() {next = new Trie[26];isEnd = false;}public void insert(String s) {Trie curPos = this;for (int i = s.length() - 1; i >= 0; --i) {int t = s.charAt(i) - 'a';if (curPos.next[t] == null) {curPos.next[t] = new Trie();}curPos = curPos.next[t];}curPos.isEnd = true;}
}