【leetcode 2707. 字符串中的额外字符】动态规划 & 字典树

2707. 字符串中的额外字符

题目描述

给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串，每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。

请你采取最优策略分割 s ，使剩下的字符 最少 。

动态规划

这是一个比较典型的动态规划问题，只要能够想到利用dp[i]表示s.substr(0,i)（也就时s从0开始，长度为i的子字符串）剩下的字符的最少数量，比较容易就能找到如下规律：

• s.substr(0,i)的后缀与dictionary中一个长度为l的单词匹配，那么dp[i] = dp[i - l]。
• 如果s.substr(0,i)与dictionary中所有单词都不匹配，那么个dp[i] = dp[i - 1] + 1。

据此容易写出如下代码：

class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        int s_len = s.size();
        vector<int> dp(s_len + 1, 0);
        
        for(int i = 1;i <= s_len;++i) {
            dp[i] = dp[i - 1] + 1;
            for(auto it = dictionary.begin();it != dictionary.end();++it) {
                int w_len = (*it).size();
                if(w_len <= i && s.substr(i - w_len, w_len) == *it) {
                    dp[i] = min(dp[i], dp[i - w_len]);
                }
            }
        }
        return dp[s_len];
    }
};

结果还算不错

利用字典树优化

上面思路中提到，要通过字符串的后缀与字典中单词是否匹配来判断动态规划的路径。

这容易让人想到字典树，也就是前缀树。关于字典树，我写过一篇字典树分析及实现。

虽然称为前缀树，经过一些变形也可以用来快速判断后缀是否匹配。

进而优化上面的实现，算是用空间换时间。

代码的改变还是比较大的，具体实现如下

struct Trie {
    struct Trie* children[26];
    bool isEnd;
    Trie() {
        isEnd = false;
        memset(children, 0, 26 * sizeof(struct Trie*));
    }
};
class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        struct Trie *root = new struct Trie();
        int s_len = s.size();
        vector<int> dp(s_len + 1, 0);
        
        // 插入字典中的单词 
        for(auto it = dictionary.begin();it != dictionary.end();++it) {
            int d_len = it->size();
            struct Trie *p = root;
            // 倒序插入单词，方便匹配后缀
            for(int i = d_len - 1;i >= 0;--i) {
                int idx = (*it)[i] - 'a';
                if(p->children[idx] == nullptr) {
                    p->children[idx] = new struct Trie();
                }
                p = p->children[idx];
            }
            p->isEnd = true;
        }
        for(int i = 1;i <= s_len;++i) {
            dp[i] = dp[i - 1] + 1;
            struct Trie *p = root;
            for(int j = i - 1;j >= 0;--j) {
                int idx = s[j] - 'a';
                if(p == nullptr || p->children[idx] == nullptr) {
                    // 如果中间有字符不匹配，后续就不可能有更长单词能匹配后缀了
                    break;
                }
                p = p->children[idx];
                if(p->isEnd) {
                    dp[i] = min(dp[i], dp[j]);
                }
            }
        }
        return dp[s_len];
    }
};

结果如下图，虽然时间上有一定提升，但空间占用却增加了一倍

ps：需要注意的是，这里用到了new去动态分配内存，理论上是要利用delete手动释放内存，防止内存泄露的。