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

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

示例1:

输入:s = "leetscode", dictionary = ["leet","code","leetcode"]
输出:1
解释:将s分成两个子字符串:下标从0到3的"leet"和下标从5到8的"code"。只有1个字符没有使用(下标为4),所以我们返回1。

示例2:

输入:s = "sayhelloworld", dictionary = ["hello","world"]
输出:3
解释:将s分成两个子字符串:下标从3到7的"hello"和下标从8到12的"world"。下标为0,1和2的字符没有使用,所以我们返回3。

提示:

  • 1 <= s.length <= 50
  • 1 <= dictionary.length <= 50
  • 1 <= dictionary[i].length <= 50
  • dictionary[i]和s只包含小写英文字母
  • dictionary中的单词互不相同。

题目分析

DP: 我们定义 DP[i] 的意义为:对于母串的子串 s[0] ~ s[i] 中的额外字符数目。 那么对于母串中的第 i 位, 有两种状态:

  1. 当前字符不作为任何 Dictionary 中字符串的最后一个字符。则此字符一定不会被消去, 则 DP[i] = DP[i - 1] + 1
  2. 当前字符能够作为 Dictionary 中某些(一个或多个)字符串的最后一个字符, 则 DP[i] = min(DP[i - 1] + 1, DP[j - 1])。其中 s[j] ~ s[i]Dictionary 中的字符串。 我们可以知道:

    • DP[0] = 0
    • Ans = DP[母串.length() - 1]
    • 可以创建 Dictionary 倒序字典树优化掉哈希表

代码实现

class Solution {
public:
    int dp[100];
    unordered_set <string> st;
    int minExtraChar(string s, vector<string>& dictionary) {
        int n = s.length();
        for(auto& dict : dictionary) st.insert(dict);
        s = " " + s;
        for(int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1] + 1;
            for(int j = 1; j <= i; ++j) {
                if(st.find(s.substr(j, i - j + 1)) != st.end()) dp[i] = min(dp[i], dp[j - 1]);
            }
        }
        return dp[n];
    }
};
分类: DPHashTrie

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status