字符串中的额外字符

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

/*
 * 思路：
 * 与传统的Java解决方案类似，我们依然使用动态规划来解决问题。
 * 不同的是，我们将利用Java Stream API来简化代码的编写，特别是在更新dp数组的部分。
 */
import java.util.*;
import java.util.stream.*;

public class MinRemainingCharsStream {
    public int minRemainingChars(String s, List<String> dictionary) {
        int n = s.length();
        Set<String> dict = new HashSet<>(dictionary);
        int[] dp = new int[n + 1];
        Arrays.fill(dp, n);
        dp[0] = 0;

        IntStream.rangeClosed(1, n).forEach(i -> {
            IntStream.range(0, i).forEach(j -> {
                if (dict.contains(s.substring(j, i))) {
                    dp[i] = Math.min(dp[i], dp[j]);
                }
            });
            dp[i] = Math.min(dp[i], dp[i - 1] + 1);
        });

        return dp[n];
    }

    public static void main(String[] args) {
        MinRemainingCharsStream solution = new MinRemainingCharsStream();
        List<String> dictionary = Arrays.asList("leet", "code", "leetcode");
        String s = "leetscode";
        System.out.println(solution.minRemainingChars(s, dictionary)); // 输出1
    }
}

题解采用动态规划的方法来解决字符串分割问题。首先，创建一个字典 dic，将每个单词按其最后一个字符分类存储。使用动态规划数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符中未被使用的最小字符数量。遍历字符串 s 的每个字符，并检查是否有字典中的单词以该字符结束，如果是，则尝试匹配整个单词。如果匹配成功，更新 dp 数组以尝试减少未使用的字符数量。最终，dp 数组的最后一个元素 dp[n]（其中 n 是字符串 s 的长度）给出了分割后剩余的最少字符数。

O(n * m)

O(n)