面试题 17.13. 恢复空格 (JAVA)
2021-04-21 03:27
标签：算法 字母 str 没有 数据 stl bsp return 相同 哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。 示例： 输入： 思路：建立字典树的数据结构，然后使用动态规划。 字典树，又称为Trie，或Prefix Tree，一个节点的所有子孙都有相同的前缀，根结点一般为空，每个节点一般有26个孩子，对应26个英文字母 应用： (1) 自动补全 面试题 17.13. 恢复空格 (JAVA) 标签：算法 字母 str 没有 数据 stl bsp return 相同 原文地址：https://www.cnblogs.com/qionglouyuyu/p/13282156.html
dictionary = ["looked","just","like","her","brother"]
sentence = "jesslookedjustliketimherbrother"
输出： 7
解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。
提示：
(2) 拼写检查
(3) IP路由表
在IP路由表中进行路由匹配时, 要按照最长匹配前缀的原则进行匹配。
(4) T9预测文本
手机上用9格的那种输入法输入时，能够根据用户在9格上的输入,自动匹配出可能的单词。
(5) 填单词游戏
那种在横竖的格子里填单词的游戏。class Solution {
public class Node {
public Node[] dict;
public boolean isEnd;
public Node(){
this.dict = new Node[26];
this.isEnd = false;
}
}
public int respace(String[] dictionary, String sentence) {
//构造字典树
Node dummyNode = new Node();
Node currentNode;
int pos;
for(String word : dictionary){
currentNode = dummyNode;
for (int i = word.length()-1; i >= 0; i--){ //将单词倒序放入字典树(因为动态规划由后往前遍历)
pos = word.charAt(i)-‘a‘;
if(currentNode.dict[pos] == null) currentNode.dict[pos] = new Node();
currentNode = currentNode.dict[pos];
}
currentNode.isEnd = true;
}
//动态规划
int[] dp = new int[sentence.length()+1];
dp[0] = 0;
for(int i = 0; i ){
currentNode = dummyNode;
dp[i+1] = dp[i] + 1;
for(int j = i; j >= 0; j--){
pos = sentence.charAt(j)-‘a‘;
/* 动态转移方程
* 如果在sentence[j]找到单词 那么dp[i+1] = dp[j];
* 如果在sentence[j]没有找到单词 那么dp[i+1] = dp[k+1] + k-i (j*/
if(currentNode.dict[pos]!=null){
currentNode = currentNode.dict[pos];
if(currentNode.isEnd){
if (dp[j] dp[j];
//这里不需要break，因为可能存在某个单词是另一个单词的后缀，比如 her & brother
} else {
if(dp[j+1] + i-j j;
}
} else {
if(dp[j+1] + i-jj;
break;
}
}
}
return dp[sentence.length()];
}
}
文章标题：面试题 17.13. 恢复空格 (JAVA)
文章链接：http://soscw.com/index.php/essay/77421.html