给你一个字符串 word 和一个字符串数组 forbidden 。
如果一个字符串不包含 forbidden 中的任何字符串，我们称这个字符串是 合法 的。
请你返回字符串 word 的一个 最长合法子字符串 的长度。
1. 哈希
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++) {//以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;
}
};
2. 字典树
class Trie {
public:
bool isEnd;
Trie* next[26];
Trie() {
isEnd = false;
memset(next, 0, sizeof(next));
}
void insert(string word) {
Trie* node = this;
for (char c : word) {
if (node->next[c-'a'] == NULL) {
node->next[c-'a'] = new Trie();
}
node = node->next[c-'a'];
}
node->isEnd = true;
}
};
class Solution {
public:
int longestValidSubstring(string word, vector<string> &forbidden) {
Trie* tree = new Trie();
for(auto& s:forbidden)
tree->insert(s);
int ans = 0, n = word.length(), right = n-1;
for (int left = n-1 ; left >= 0; left--) {//以left为左边界的字符串
Trie* node = tree;
for (int i = left; i <=right && i < left + 10; i++) {//向右移动，不会越过上一个非法位置
node = node->next[word[i]-'a'];
if(node==NULL) break;//终止查找
if(node->isEnd){ //存在非法字符串，对于第一个匹配的非法字符串末端
right = i - 1;//记录上一个合法位置
break;
}
}
ans = max(ans, right - left + 1);//更新当前最长合法字符串
}
return ans;
}
};