最长合法子字符串的长度
给你一个字符串 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 <= 10^5\)
word 只包含小写英文字母。
\(1 <= forbidden.length <= 10^5\)
\(1 <= forbidden[i].length <= 10\)
forbidden[i] 只包含小写英文字母。
解题思路
见代码注释
Code
class Solution:
#hint1 : 1 <= forbidden.length <= 1e5 && 1 <= forbidden[i].length <= 10
#其中forbidden中字符串的数目为5次方级别的，每个字符串的长度为10
#意味着可以想暴力的解法，枚举长度10，然后哈希去查找
#朴素的解法：在枚举过程中回存在回溯
#双指针
#双指针一般有两种写法，枚举左指针为端点的最长子串（右指针不需要回溯）
#枚举右指针为端点的最长子串（左指针不回溯）
#可以使用第一个示例模拟双指针的过程
#[left,right]区间内的字符串，right往回查看10个（因为最长为10）
#找到第一个forbidden的字符串并右移左指针消掉（左指针右移就不能再左移了也就是不能回溯，要是左移必然会包含forbidden的字符串，这也是双指针的基础）
#看了灵神的视频讲解，大佬们的思路都好清晰啊,实际上还是要想挺多细节的，得多动脑，这样脑子转的快点
def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
#新学的知识点：set的是哈希表
#这样查找是否存在就是O(1)的时间复杂度，不需要遍历的O(n)时间复杂度
#但是比较键值的时间复杂度是O(M),M为10
#转化为哈希表的时间复杂度为O(L),L为sum(forbidden[i])
#总的时间复杂度为O(L + n * M ^2)
fb = set(forbidden)
left = 0
ans = 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
break
ans = max(ans,right - left + 1)
return ans
class Solution {
public:
//word 中不含有forbidden中任何字符串的最长子字符串
int longestValidSubstring(string word, vector<string>& forbidden) {
unordered_set<string> fb(forbidden.begin(),forbidden.end());
int left = 0,ans = 0;
for(int right = 0;right < word.size();right ++)
{
for(int i = right;i >= left && i > right - 10;i --)
{
if(fb.count(word.substr(i,right - i + 1)))
{
left = i + 1;
break;
}
}
ans = max(ans,right - left + 1);
}
return ans;
}
};