Problem
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
Solution
/**
* @param {string} s
* @param {string[]} dictionary
* @return {number}
*/
var minExtraChar = function(s, dictionary) {
var map = dictionary.reduce((res, item) => {
res[item] = 1;
return res;
}, {});
var dp = Array(s.length);
for (var i = s.length - 1; i >= 0; i--) {
dp[i] = (dp[i + 1] || 0) + 1;
var str = '';
for (var j = i; j < s.length; j++) {
str += s[j];
if (map[str]) {
dp[i] = Math.min(dp[i], dp[j + 1] || 0);
}
}
}
return dp[0];
};
Explain:
Bottom-up dynamic programming.
Complexity:
- Time complexity : O(n ^ 2).
- Space complexity : O(n).