class Solution {
public:
int minExtraChar(string s, vector<string>& dictionary) {
}
};
6394. 字符串中的额外字符
给你一个下标从 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 。
提示：
1 <= s.length <= 501 <= dictionary.length <= 501 <= dictionary[i].length <= 50dictionary[i] 和 s 只包含小写英文字母。dictionary 中的单词互不相同。原站题解
cpp 解法, 执行用时: 152 ms, 内存消耗: 79.2 MB, 提交时间: 2024-01-09 00:05:43
class Solution {
public:
int minExtraChar(string s, vector<string> &dictionary) {
unordered_set<string> set(dictionary.begin(), dictionary.end());
int n = s.size();
vector<int> f(n + 1);
for (int i = 0; i < n; i++) {
f[i + 1] = f[i] + 1; // 不选
for (int j = 0; j <= i; j++) { // 枚举选哪个
if (set.count(s.substr(j, i - j + 1))) {
f[i + 1] = min(f[i + 1], f[j]);
}
}
}
return f[n];
}
};
java 解法, 执行用时: 45 ms, 内存消耗: 44.3 MB, 提交时间: 2024-01-09 00:05:27
class Solution {
public int minExtraChar(String s, String[] dictionary) {
var set = new HashSet<String>(dictionary.length);
for (var str : dictionary) set.add(str);
int n = s.length();
var f = new int[n + 1];
for (int i = 0; i < n; i++) {
f[i + 1] = f[i] + 1; // 不选
for (int j = 0; j <= i; j++) { // 枚举选哪个
if (set.contains(s.substring(j, i + 1))) {
f[i + 1] = Math.min(f[i + 1], f[j]);
}
}
}
return f[n];
}
}
python3 解法, 执行用时: 156 ms, 内存消耗: 16.6 MB, 提交时间: 2023-05-28 10:31:34
class Solution:
def minExtraChar(self, s: str, dictionary: List[str]) -> int:
@cache
def dfs(s_):
if s_ == "": return 0
return min([dfs(s_[len(d):]) for d in dictionary if s_.startswith(d)] + [1 + dfs(s_[1:])])
return dfs(s)
python3 解法, 执行用时: 152 ms, 内存消耗: 16 MB, 提交时间: 2023-05-28 10:31:06
class Solution:
def minExtraChar(self, s: str, dictionary: List[str]) -> int:
d = set(dictionary)
n = len(s)
f = [0] * (n + 1)
for i in range(n):
f[i + 1] = f[i] + 1 # 不选
for j in range(i + 1): # 枚举选哪个
if s[j:i + 1] in d:
f[i + 1] = min(f[i + 1], f[j])
return f[n]
golang 解法, 执行用时: 36 ms, 内存消耗: 6.9 MB, 提交时间: 2023-05-28 10:30:48
func minExtraChar(s string, dictionary []string) int {
has := map[string]bool{}
for _, s := range dictionary {
has[s] = true
}
n := len(s)
f := make([]int, n+1)
for i := 0; i < n; i++ {
f[i+1] = f[i] + 1 // 不选
for j := 0; j <= i; j++ { // 枚举选哪个
if has[s[j:i+1]] {
f[i+1] = min(f[i+1], f[j])
}
}
}
return f[n]
}
func min(a, b int) int { if b < a { return b }; return a }
golang 解法, 执行用时: 32 ms, 内存消耗: 6.9 MB, 提交时间: 2023-05-28 10:30:32
func minExtraChar(s string, dictionary []string) int {
has := map[string]bool{}
for _, s := range dictionary {
has[s] = true
}
n := len(s)
memo := make([]int, n)
for i := range memo {
memo[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if i < 0 {
return 0
}
p := &memo[i]
if *p != -1 {
return *p
}
// 不选
res := dfs(i-1) + 1
// 枚举选哪个
for j := 0; j <= i; j++ {
if has[s[j:i+1]] {
res = min(res, dfs(j-1))
}
}
*p = res
return res
}
return dfs(n - 1)
}
func min(a, b int) int { if b < a { return b }; return a }
python3 解法, 执行用时: 180 ms, 内存消耗: 16.7 MB, 提交时间: 2023-05-28 10:30:07
# 记忆化搜索
class Solution:
def minExtraChar(self, s: str, dictionary: List[str]) -> int:
d = set(dictionary)
@cache
def dfs(i: int) -> int: # s前i个字符的子问题
if i < 0: return 0
res = dfs(i - 1) + 1 # 不选
for j in range(i + 1): # 枚举选哪个
if s[j:i + 1] in d:
res = min(res, dfs(j - 1))
return res
return dfs(len(s) - 1)