面试题 17.13. 恢复空格

面试题 17.13. 恢复空格

dp

自己写出来了，不容易...

class Solution {
public:
    int respace(vector<string>& dictionary, string sentence) {
        unordered_set<string> dict;
        for(auto str:dictionary) dict.insert(str);
        int n=sentence.size();
        int dp[n+1];
        memset(dp,0,sizeof dp);

        for(int i=1;i<=n;i++){
            dp[i]=dp[i-1]+1;
            for(int j=0;j<i;j++){
                string tmp=sentence.substr(j,i-j);
                // 找到了
                if(dict.find(tmp)!=dict.end()){
                    dp[i]=min(dp[i],dp[i-tmp.size()]);
                }
            }
        }
        
        return dp[n];
    }
};

别人的写法
应该比我的快，只用找在字典里的就行，也不用多维护一个集合

class Solution {
public:
    int respace(vector<string>& dictionary, string sentence) {
        int n=sentence.size();
        int dp[n+1];
        dp[0]=0;
        for(int i=1;i<=n;++i){
            dp[i]=dp[i-1]+1;
            for(auto& word:dictionary){
                if(word.size()<=i){
                    if(word==sentence.substr(i-word.size(),word.size()))
                        dp[i]=min(dp[i],dp[i-word.size()]);
                }
            }
        }
        return dp[n];
    }
};