【Leetcode 2707】字符串中的额外字符 —— 动态规划

2707. 字符串中的额外字符

给你一个下标从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 。

题目分析

经典动态规划问题，更多案例可见 Leetcode 动态规划详解

我们可以使用动态规划解决本题，解题思路：

1. 状态定义：把s[i?1]当做是额外字符，d[i] = d[i?1] + 1
2. 状态转移方程：遍历所有的j(j∈[0,i?1])，如果子字符串s[j...i?1]存在于dictionary中，那么`d[i] = min d[j]
3. 初始状态d[0] = 0，最终答案为d[n]

动态规划一般用于求解具有重叠子问题和最优子结构的问题，例如最长公共子序列、背包问题、最短路径等。重叠子问题指的是在求解问题的过程中，多次用到相同的子问题，最优子结构指的是问题的最优解可以通过子问题的最优解来构造

public int minExtraChar(String s, String[] dictionary) {
	int n = s.length();
	int[] d = new int[n + 1];
	Arrays.fill(d, Integer.MAX_VALUE);
	Set<String> set = new HashSet<>();
	for (String str : dictionary) {
		set.add(str);
	}

	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 (set.contains(s.substring(j, i))) {
				d[i] = Math.min(d[i], d[j]);
			}
		}
	}
	return d[n];
}