面试题 17.13. Re-Space LCCI(Leetcode每日一题-2020.07.09）

本文主要是介绍面试题 17.13. Re-Space LCCI(Leetcode每日一题-2020.07.09），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem

Oh, no! You have accidentally removed all spaces, punctuation, and capitalization in a lengthy document. A sentence like “I reset the computer. It still didn’t boot!” became "iresetthecomputeritstilldidntboot’’. You’ll deal with the punctuation and capi­talization later; right now you need to re-insert the spaces. Most of the words are in a dictionary but a few are not. Given a dictionary (a list of strings) and the document (a string), design an algorithm to unconcatenate the document in a way that minimizes the number of unrecognized characters. Return the number of unrecognized characters.

Note: This problem is slightly different from the original one in the book.

• 0 <= len(sentence) <= 1000
• The total number of characters in dictionary is less than or equal to 150000.
• There are only lowercase letters in dictionary and sentence.

Example

Input:
dictionary = [“looked”,“just”,“like”,“her”,“brother”]
sentence = “jesslookedjustliketimherbrother”
Output: 7
Explanation: After unconcatenating, we got “jess looked just like tim her brother”, which containing 7 unrecognized characters.

Solution

Trie + DP
不会！

class Trie {
public:Trie* next[26] = {nullptr};bool isEnd;Trie() {isEnd = false;}void insert(string s) {Trie* curPos = this;for (int i = s.length() - 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.length(), inf = 0x3f3f3f3f;Trie* root = new Trie();for (auto& word: dictionary) {root->insert(word);}vector<int> dp(n + 1, inf);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[j - 1] - 'a';if (curPos->next[t] == nullptr) {break;} else if (curPos->next[t]->isEnd) {dp[i] = min(dp[i], dp[j - 1]);}if (dp[i] == 0) {break;}curPos = curPos->next[t];}}return dp[n];}
};

这篇关于面试题 17.13. Re-Space LCCI(Leetcode每日一题-2020.07.09）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---