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]
ands
consists of only lowercase English lettersdictionary
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 }
- Characters LeetCode String Extra 2707characters leetcode string extra characters substrings unique string 字符 字符串leetcode 2707 subsequence characters leetcode append characters leetcode formed words characters substring repeating leetcode characters leetcode stream 1032 leetcode largest number string 2707 difference leetcode string 2451