題目描述
描述：哦，不！你不小心把一個(gè)長(zhǎng)篇文章中的空格、標(biāo)點(diǎn)都刪掉了，并且大寫(xiě)也弄成了小寫(xiě)。像句子"I reset the computer. It still didn’t boot!“已經(jīng)變成了"iresetthecomputeritstilldidntboot”。在處理標(biāo)點(diǎn)符號(hào)和大小寫(xiě)之前，你得先把它斷成詞語(yǔ)。當(dāng)然了，你有一本厚厚的詞典dictionary，不過(guò)，有些詞沒(méi)在詞典里。假設(shè)文章用sentence表示，設(shè)計(jì)一個(gè)算法，把文章斷開(kāi)，要求未識(shí)別的字符最少，返回未識(shí)別的字符數(shù)。
注意：本題相對(duì)原題稍作改動(dòng)，只需返回未識(shí)別的字符數(shù)
示例：
輸入：
dictionary = ["looked","just","like","her","brother"]
sentence = "jesslookedjustliketimherbrother"
輸出： 7
解釋?zhuān)?斷句后為"jess looked just like tim her brother"，共7個(gè)未識(shí)別字符。
提示：
0 <= len(sentence) <= 1000
dictionary中總字符數(shù)不超過(guò) 150000。
你可以認(rèn)為dictionary和sentence中只包含小寫(xiě)字母。
解題思路
思路：最直觀的想法是，動(dòng)態(tài)規(guī)劃+字典樹(shù)。使用dp[i]表示長(zhǎng)度為i的字符串的最少未識(shí)別字符，如果下標(biāo)0i-1(長(zhǎng)度1i)之間未匹配，則dp[i]=dp[i-1]+1，反之如果下標(biāo)j-1i-1(長(zhǎng)度ji)之間發(fā)生匹配，則dp[i]=dp[j-1]+1，其中字典樹(shù)需要逆序構(gòu)建喔！
class Trie {
public:
//下一個(gè)字母
Trie* next[26];
//該字符是否是該單詞的結(jié)束位置
bool isEnd;
//前綴樹(shù)類(lèi)的構(gòu)造函數(shù)
Trie(){
isEnd=false;
memset(next,0,sizeof(next));
}
//向字典樹(shù)中插入單詞(可根據(jù)需求選擇正序或者逆序插入)
void insert(string s)
{
//逆序插入
Trie* curPos=this;
for(int i=s.size()-1;i>=0;i--)
{
int t=s[i]-'a';
if(curPos->next[t]==nullptr)
curPos->next[t]=new Trie();
curPos=curPos->next[t];
}
curPos->isEnd=true;
}
};
class Solution {
public:
int respace(vector<string>& dictionary, string sentence) {
int n=sentence.size();
int m=dictionary.size();
//創(chuàng)建字典樹(shù)對(duì)象 使用指針root指向該對(duì)象
Trie* root=new Trie();
//構(gòu)建字典樹(shù)
for(auto dic:dictionary)
{
root->insert(dic);
}
//dp[i]表示以長(zhǎng)度為i結(jié)尾的最少未識(shí)別字符
vector<int> dp(n+1,INT_MAX);
//長(zhǎng)度為0的字符串未識(shí)別的為0
dp[0]=0;
//i表示第幾個(gè)字符
for(int i=1;i<=n;i++)
{
dp[i]=dp[i-1]+1;
Trie* curPos=root;
//j表示第幾個(gè)字符
for(int j=i;j>=1;j--)
{
//字符對(duì)應(yīng)的下標(biāo)
int t=sentence[j-1]-'a';
//如果當(dāng)前字符在字典樹(shù)中不存在則直接退出
if(curPos->next[t]==nullptr)
break;
//如果當(dāng)前字符在字典樹(shù)中且已經(jīng)結(jié)束則求取最小長(zhǎng)度
else if(curPos->next[t]->isEnd)
dp[i]=min(dp[i],dp[j-1]);
curPos=curPos->next[t];
}
}
return dp[n];
}
};
總結(jié)：注意字典樹(shù)的數(shù)據(jù)結(jié)構(gòu)編寫(xiě)方式?。?！root->insert?。?！
字典樹(shù)介紹
- 實(shí)現(xiàn) Trie (前綴樹(shù))
前綴樹(shù) 是一種樹(shù)形數(shù)據(jù)結(jié)構(gòu)，用于高效地存儲(chǔ)和檢索字符串?dāng)?shù)據(jù)集中的鍵。這一數(shù)據(jù)結(jié)構(gòu)有相當(dāng)多的應(yīng)用情景，例如自動(dòng)補(bǔ)完和拼寫(xiě)檢查。
請(qǐng)你實(shí)現(xiàn) Trie 類(lèi)：
Trie() 初始化前綴樹(shù)對(duì)象。
void insert(String word) 向前綴樹(shù)中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前綴樹(shù)中，返回 true（即，在檢索之前已經(jīng)插入）；否則，返回 false 。
boolean startsWith(String prefix) 如果之前已經(jīng)插入的字符串 word 的前綴之一為 prefix ，返回 true ；否則，返回 false 。
示例：
輸入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
輸出
[null, null, true, false, true, null, true]
解釋
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
提示：
1 <= word.length, prefix.length <= 2000
word 和 prefix 僅由小寫(xiě)英文字母組成
insert、search 和 startsWith 調(diào)用次數(shù) 總計(jì) 不超過(guò) 3 * 104 次
思路：最直觀的想法是，字典樹(shù)。字典樹(shù)，一次建樹(shù)，多次查詢(xún)。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-500508.html
class Trie {
private:
bool isEnd; //標(biāo)記是否為單詞結(jié)尾
Trie* next[26]; //標(biāo)記下一個(gè)節(jié)點(diǎn)可能是什么 分別是a,b,c,d...
public:
Trie() {
isEnd=false;
memset(next,0,sizeof(next));
}
void insert(string word) {
//首先指向當(dāng)前這棵樹(shù)
Trie* node=this;
//遍歷單詞
for(char c:word)
{
//如果對(duì)應(yīng)為空則新建
if(node->next[c-'a']==NULL)
node->next[c-'a']=new Trie();
//然后將節(jié)點(diǎn)指向當(dāng)前(為下一次準(zhǔn)備)
node=node->next[c-'a'];
}
//置單詞結(jié)束標(biāo)志
node->isEnd=true;
}
bool search(string word) {
//首先指向當(dāng)前這棵樹(shù)
Trie* node=this;
for(char c:word)
{
node=node->next[c-'a'];
if(node==NULL)
return false;
}
return node->isEnd;
}
bool startsWith(string prefix) {
//首先指向當(dāng)前這棵樹(shù)
Trie* node=this;
for(char c:prefix)
{
node=node->next[c-'a'];
if(node==NULL)
return false;
}
return true;
}
};
總結(jié)：字典樹(shù)一般用于單詞查找和前綴匹配。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-500508.html
到了這里，關(guān)于【程序員面試金典】面試題 17.13. 恢復(fù)空格的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
