2024.1.9每日一题

2024-01-09 19:38:37

LeetCode

2707.字符串中的额外字符

2707. 字符串中的额外字符 - 力扣(LeetCode)

题目描述

给你一个下标从 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 中的单词互不相同。

思路

动态规划

代码

C++
class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        int n = s.size();
        vector<int> d(n + 1, INT_MAX);
        unordered_map<string,int> mp;
        for(auto s : dictionary){
            mp[s]++;
        }
        d[0] = 0;
        for(int i = 1; i <= n; i++){
            d[i] = d[i - 1] + 1;
            for(int j = i - 1; j >= 0; j--){
                if(mp.count(s.substr(j,i - j))){
                    d[i] = min(d[i],d[j]);
                }
            }
        }
        return d[n];
    }
};
Java
class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        int n = s.length();
        int[] d = new int[n + 1];
        Arrays.fill(d,Integer.MAX_VALUE);
        Map<String,Integer> map = new HashMap<String,Integer>();
        for(String str : dictionary){
            map.put(str,map.getOrDefault(str,0) + 1);
        }
        d[0] = 0;
        for(int i = 1; i <= n; i++){
            d[i] = d[i - 1] + 1;
            for(int j = i - 1; j >= 0; j--){
                if(map.containsKey(s.substring(j,i))){
                    d[i] = Math.min(d[i],d[j]);
                }
            }
        }
        return d[n];
    }
}

image-20240109184035567

文章来源:https://blog.csdn.net/ysk_0904/article/details/135487389
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。