LeetCode 2707. 字符串中的额外字符

一、题目

1、题目描述

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

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

2、接口描述

​

class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        
    }
};

3、原题链接

2707. 字符串中的额外字符

二、解题报告

1、思路分析

和上周周赛题目类似，也是分割字符串，我们可以用动态规划将问题划分为子问题

定义状态dp[i]为前i个字符最优划分后的最少额外字符，那么有转移方程：

dp[i] = dp[ i -1]，将第i个字符作为额外字符

dp[i] = min(dp[i] , dp[j - 1])，其中第j个字符到第i个字符在字典中

最终返回dp[n]即可

进行状态转移，如果暴力计算子串是否在字典中，显然复杂度过高

如果将字典中字符串存入哈希表，那么每次状态转移为n * 2，因为我们要从(i , i)计算到(1 , i)

这里就涉及到查询字符串优化的常用策略，将目标字符串倒序存入字典树，然后倒序查询可以满足一次遍历完成查询，关于字典树见：Trie树/字典树的原理及实现[C/C++]-CSDN博客

2、复杂度

时间复杂度：O(n^2 + ml) 空间复杂度：O(m l * 26)

3、代码详解

​

class Solution
{
public:
    struct Node
    {
        bool isword = false;
        unordered_map<char, Node *> child;
    } root;
    void insert(string &s)
    {
        Node *cur = &root;
        for (int i = s.size() - 1; i >= 0; i--)
        {
            if (!cur->child.count(s[i]))
                cur->child[s[i]] = new Node;
            cur = cur->child[s[i]];
        }
        cur->isword = true;
    }
    int minExtraChar(string s, vector<string> &dictionary)
    {
        root.child.clear();
        for (auto &x : dictionary)
            insert(x);
        int n = s.size();
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            dp[i] = dp[i - 1] + 1;
            Node *cur = &root;
            for (int j = i; j >= 1; j--)
            {
                if (!cur->child.count(s[j - 1]))
                    break;

                cur = cur->child[s[j - 1]];
                if (cur->isword)
                    dp[i] = min(dp[i], dp[j - 1]);
            }
        }

        return dp[n];
    }
};