【Py/Java/C++三种语言详解】LeetCode每日一题240109【动态规划】LeetCode2707题、字符串中的额外字符

2024-01-09 13:58:12

题目描述

给你一个下标从 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问题,类似题目包括LeetCode137、单词拆分LeetCode472、连接词

这类问题的核心点在于思考动态转移过程。

简单举例

以示例二为例,已知s的子字符串"say"不位于dictionary中,而接下来的一个子字符串"hello"位于dictionary中。

s的以"o"为结尾的子字符串"sayhello"可以由以"y"为结尾的子字符串"say"和接下来的"hello"拼接构成。

那么切割"sayhello"的剩余字符数,和切割"say"的剩余字符串相等。

哈希集合进行查找

由于涉及到子串的查找,故将数组dictionary转化为哈希集合word_set,方便在O(1)的复杂度内完成查找。即

word_set = set(dictionary)

动态规划三部曲

我们考虑动态规划三部曲:

  1. dp数组的含义是什么?
  • 构建长度为(n+1)dp数组
  • dp[i]表示以s[i-1]为结尾的子字符串s[:i],分割后剩下的字符的最少数目(即题目设问)。
  • dp[0]表示空串""的情况。
  1. 动态转移方程是什么?
  • 使用双重循环枚举所有子串s[i:j],即枚举子串的终点j和起点i
  • 考虑子串s[:i]和子串s[:j]之间的关系(i < j
    • 如果子串s[i:j]位于word_set中。则s[:j]可以由s[:i]加上s[i:j]构成
      • dp[j]可以由dp[i]转移过来。
      • 存在dp[j] = min(dp[i], dp[j])
    • 如果子串s[i:j]不位于word_set中。则可认为s[:j]可以由s[:i]加上子串s[i:j]中的每一个单个字符构成,s[i:j]中一共存在j-i个单字符。
      • dp[j]可以由dp[i]+j-i转移过来
      • 存在dp[j] = min(dp[i]+j-i, dp[j])

上述逻辑整理为代码即

for j in range(1, (n+1)):
    for i in range(j):
        if s[i:j] in word_set:
            dp[j] = min(dp[i], dp[j])
        else:
            dp[j] = min(dp[i]+j-i, dp[j])
  1. dp数组如何初始化?
  • 初始化dp[i] = i,表示在初始状态下,每一个字符都进行分割。对于以第i个字符为结尾的子串s[:i],一共分割出i个字符。
dp = [i for i in range(n+1)]

代码

python

# dp:O(N^3)复杂度
class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        word_set = set(dictionary)
        n = len(s)
        # 初始化长度为(n+1)的dp数组
        # dp[i]表示以s[i-1]为结尾的子字符串s[:i]
        # 分割后剩下的字符的最少数目
        # 初始化dp[i] = i,表示每一个字符都进行分割
        dp = [i for i in range(n+1)]
        # 遍历结束位置j
        for j in range(1, (n+1)):
            # 遍历子字符串的开始位置i
            for i in range(j):
                # 如果子串s[i:j]位于word_set中
                # 则s[:j]可以由s[:i]加上s[i:j]构成
                # 故dp[j]可以由dp[i]转移过来
                if s[i:j] in word_set:
                    dp[j] = min(dp[i], dp[j])
                # 否则,可认为s[:j]可以由s[:i]加上子串s[i:j]中的j-i个单个字符构成
                # 故dp[j]可以由dp[i]+j-i转移过来
                else:
                    dp[j] = min(dp[i]+j-i, dp[j])
        # 最后返回dp[n]
        return dp[n]

java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        Set<String> wordSet = new HashSet<>();
        for (String word : dictionary) {
            wordSet.add(word);
        }
        
        int n = s.length();
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = i;
        }
        
        for (int j = 1; j <= n; j++) {
            for (int i = 0; i < j; i++) {
                if (wordSet.contains(s.substring(i, j))) {
                    dp[j] = Math.min(dp[i], dp[j]);
                } else {
                    dp[j] = Math.min(dp[i] + j - i, dp[j]);
                }
            }
        }
        
        return dp[n];
    }
}

cpp

#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        unordered_set<string> wordSet(dictionary.begin(), dictionary.end());
        int n = s.length();
        vector<int> dp(n + 1, 0);
        for (int i = 0; i <= n; i++) {
            dp[i] = i;
        }
        
        for (int j = 1; j <= n; j++) {
            for (int i = 0; i < j; i++) {
                if (wordSet.find(s.substr(i, j - i)) != wordSet.end()) {
                    dp[j] = min(dp[i], dp[j]);
                } else {
                    dp[j] = min(dp[i] + j - i, dp[j]);
                }
            }
        }
        
        return dp[n];
    }
};

时空复杂度

时间复杂度:O(N^3)。枚举子串的终点j和起点i需要双重for循环,复杂度为O(N^2),获得子串切片s[i:j]的时间复杂度也为O(N)。故总时间复杂度为O(N^3)Ns的长度。

空间复杂度:O(M)word_set所需空间,M为dictionary的长度。


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

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