class Solution {
public:
int longestValidSubstring(string word, vector<string>& forbidden) {
}
};
6924. 最长合法子字符串的长度
给你一个字符串 word 和一个字符串数组 forbidden 。
如果一个字符串不包含 forbidden 中的任何字符串，我们称这个字符串是 合法 的。
请你返回字符串 word 的一个 最长合法子字符串 的长度。
子字符串 指的是一个字符串中一段连续的字符，它可以为空。
示例 1：
输入：word = "cbaaaabc", forbidden = ["aaa","cb"] 输出：4 解释：总共有 9 个合法子字符串："c" ，"b" ，"a" ，"ba" ，"aa" ，"bc" ，"baa" ，"aab" 和 "aabc" 。最长合法子字符串的长度为 4 。 其他子字符串都要么包含 "aaa" ，要么包含 "cb" 。
示例 2：
输入：word = "leetcode", forbidden = ["de","le","e"] 输出：4 解释：总共有 11 个合法子字符串："l" ，"t" ，"c" ，"o" ，"d" ，"tc" ，"co" ，"od" ，"tco" ，"cod" 和 "tcod" 。最长合法子字符串的长度为 4 。 所有其他子字符串都至少包含 "de" ，"le" 和 "e" 之一。
提示：
1 <= word.length <= 105word 只包含小写英文字母。1 <= forbidden.length <= 1051 <= forbidden[i].length <= 10forbidden[i] 只包含小写英文字母。原站题解
cpp 解法, 执行用时: 536 ms, 内存消耗: 115.4 MB, 提交时间: 2023-07-17 11:09:13
class Solution {
public:
int longestValidSubstring(string word, vector<string> &forbidden) {
unordered_set<string> fb{forbidden.begin(), forbidden.end()};
int ans = 0, left = 0, n = word.length();
for (int right = 0; right < n; right++) {
for (int i = right; i >= left && i > right - 10; i--) {
if (fb.count(word.substr(i, right - i + 1))) {
left = i + 1; // 当子串右端点 >= right 时，合法子串一定不能包含 word[i]
break;
}
}
ans = max(ans, right - left + 1);
}
return ans;
}
};
javascript 解法, 执行用时: 364 ms, 内存消耗: 72.6 MB, 提交时间: 2023-07-17 11:08:39
/**
* @param {string} word
* @param {string[]} forbidden
* @return {number}
*/
var longestValidSubstring = function (word, forbidden) {
let fb = new Set();
for (const f of forbidden) fb.add(f);
const n = word.length;
let ans = 0, left = 0;
for (let right = 0; right < n; right++) {
for (let i = right; i >= left && i > right - 10; i--) {
if (fb.has(word.substring(i, right + 1))) {
left = i + 1; // 当子串右端点 >= right 时，合法子串一定不能包含 word[i]
break;
}
}
ans = Math.max(ans, right - left + 1);
}
return ans;
};
golang 解法, 执行用时: 140 ms, 内存消耗: 12.2 MB, 提交时间: 2023-07-17 11:08:21
func longestValidSubstring(word string, forbidden []string) (ans int) {
has := make(map[string]bool, len(forbidden))
for _, s := range forbidden {
has[s] = true
}
left := 0
for right := range word {
for i := right; i >= left && i > right-10; i-- {
if has[word[i:right+1]] {
left = i + 1 // 当子串右端点 >= right 时，合法子串一定不能包含 word[i]
break
}
}
ans = max(ans, right-left+1)
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
java 解法, 执行用时: 174 ms, 内存消耗: 60.2 MB, 提交时间: 2023-07-17 11:07:54
class Solution {
public int longestValidSubstring(String word, List<String> forbidden) {
var fb = new HashSet<String>();
fb.addAll(forbidden);
int ans = 0, left = 0, n = word.length();
for (int right = 0; right < n; right++) {
for (int i = right; i >= left && i > right - 10; i--) {
if (fb.contains(word.substring(i, right + 1))) {
left = i + 1; // 当子串右端点 >= right 时，合法子串一定不能包含 word[i]
break;
}
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
python3 解法, 执行用时: 1192 ms, 内存消耗: 31.3 MB, 提交时间: 2023-07-17 11:07:39
# 哈希表 + 双指针
class Solution:
def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
fb = set(forbidden)
ans = left = 0
for right in range(len(word)):
for i in range(right, max(right - 10, left - 1), -1):
if word[i: right + 1] in fb:
left = i + 1 # 当子串右端点 >= right 时，合法子串一定不能包含 word[i]
break
ans = max(ans, right - left + 1)
return ans