山东建站管理系统,抖音开放平台账号能登录抖音吗,黔西南建设厅网站,网站开发新闻一、题目
1、题目描述 给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串#xff0c;每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。 请你采取最优策略分割 s #xff…一、题目
1、题目描述 给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。 请你采取最优策略分割 s 使剩下的字符 最少 。 2、接口描述
class Solution {
public:int minExtraChar(string s, vectorstring 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_mapchar, 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, vectorstring dictionary){root.child.clear();for (auto x : dictionary)insert(x);int n s.size();vectorint 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];}
};
