[LeetCode] 2707. Extra Characters in a String

CNoodle / 2023-09-03 / 原文

You are given a 0-indexed string s and a dictionary of words dictionary. You have to break s into one or more non-overlapping substrings such that each substring is present in dictionary. There may be some extra characters in s which are not present in any of the substrings.

Return the minimum number of extra characters left over if you break up s optimally.

Example 1:

Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
Output: 1
Explanation: We can break s in two substrings: "leet" from index 0 to 3 and "code" from index 5 to 8. There is only 1 unused character (at index 4), so we return 1.

Example 2:

Input: s = "sayhelloworld", dictionary = ["hello","world"]
Output: 3
Explanation: We can break s in two substrings: "hello" from index 3 to 7 and "world" from index 8 to 12. The characters at indices 0, 1, 2 are not used in any substring and thus are considered as extra characters. Hence, we return 3.

Constraints:

1 <= s.length <= 50
1 <= dictionary.length <= 50
1 <= dictionary[i].length <= 50
dictionary[i] and s consists of only lowercase English letters
dictionary contains distinct words

字符串中的额外字符。

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

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

思路是动态规划。这道题有些类似139题。思路可以直接参考139题，这道题 dp 的定义是长度为 [i, end) 的子串被分割后剩下的字符的个数。

DP自上而下

 1 class Solution {
 2     int[] dp = new int[51];
 3 
 4     public int minExtraChar(String s, String[] dictionary) {
 5         Arrays.fill(dp, -1);
 6         return helper(s, dictionary, 0);
 7     }
 8 
 9     private int helper(String s, String[] dictionary, int i) {
10         if (i == s.length()) {
11             return 0;
12         }
13         if (dp[i] == -1) {
14             dp[i] = 1 + helper(s, dictionary, i + 1);
15             for (String w : dictionary) {
16                 if (i + w.length() <= s.length() && s.substring(i, i + w.length()).equals(w)) {
17                     dp[i] = Math.min(dp[i], helper(s, dictionary, i + w.length()));
18                 }
19             }
20         }
21         return dp[i];
22     }
23 }

DP自下而上

 1 class Solution {
 2     public int minExtraChar(String s, String[] dictionary) {
 3         int[] dp = new int[51];
 4         int n = s.length();
 5         for (int i = n - 1; i >= 0; i--) {
 6             dp[i] = 1 + dp[i + 1];
 7             for (String w : dictionary) {
 8                 if (i + w.length() <= s.length() && s.substring(i, i + w.length()).equals(w)) {
 9                     dp[i] = Math.min(dp[i], dp[i + w.length()]);
10                 }
11             }
12         }
13         return dp[0];
14     }
15 }