面试题 17.13. 恢复空格

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

解:这个题挺难得 记录下最简单的动态规划写法

分析：拿到题目，先想贪心能不能做，显然不行。比如给定字符串：abcdef，字典：["abcd", "ab", "def"]，贪心匹配是 abcd ef，有2个字符未匹配。显然有更优匹配策略： ab c def ，只有 1 个字符未匹配。所以这题需要用动态规划来解决（怎么思考一个题目可不可以用 dp 来解决，先假设 dp 表达含义，再想转移方程，很多时候自然而然就出来了）。

1、状态定义：
dp[i] 表示字符串的前 i 个字符的最少未匹配数。

2、状态转移：
假设当前我们已经考虑完了前 i 个字符了，对于前 i + 1 个字符对应的最少未匹配数：

第 i + 1 个字符未匹配，则 dp[i + 1] = dp[i] + 1，即不匹配数加 1;
遍历前 i 个字符，若以其中某一个下标 idx 为开头、以第 i + 1 个字符为结尾的字符串正好在词典里，则 dp[i] = min(dp[i], dp[idx]) 更新 dp[i]。

class Solution {
public:
        int respace(vector<string>& dictionary, string sentence) {
        set<string> set_dict(dictionary.begin(),dictionary.end());
        int n=sentence.size();
        vector<int> dp(n+1,0);

        for(int i=1;i<=n;i++)
        {
            dp[i]=dp[i-1]+1;
            for(int index=0;index<i;index++)
            {
                if(set_dict.find(sentence.substr(index,i-index))!=set_dict.end())
                {
                    dp[i]=min(dp[i],dp[index]);
                }
            }
        }
        return dp[n];
    }
};

但是会超时。。。