程序员面试金典 - 面试题 17.13. 恢复空格（DP+Trie树）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了程序员面试金典 - 面试题 17.13. 恢复空格（DP+Trie树），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3164字，纯文字阅读大概需要5分钟。

内容图文

文章目录

• 1. 题目
• 2. 解题
• 2.1 动态规划
• 2.2 Trie树

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

内容总结

以上是互联网集市为您收集整理的程序员面试金典 - 面试题 17.13. 恢复空格（DP+Trie树）全部内容，希望文章能够帮你解决程序员面试金典 - 面试题 17.13. 恢复空格（DP+Trie树）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---