LeetCode 2781. 最长合法子字符串的长度 C#
原题链接
困难
作者:
hpstory
,
2023-07-17 10:58:44
,
所有人可见
,
阅读 68
C# 双指针代码
public class Solution {
public int LongestValidSubstring(string word, IList<string> forbidden) {
int n = word.Length, j = 0, result = 0;
HashSet<string> set = new HashSet<string>(forbidden);
for (int i = 0; i < n; i++){
int k = i, t = Math.Max(j, i - 10);
while (k >= t){
// 倒序枚举, 只要在forbidden中出现前面的子串就可以不用考虑了
if (set.Contains(word.Substring(k, i - k + 1))){
j = k + 1;
break;
}
k--;
}
result = Math.Max(result, i - j + 1);
}
return result;
}
}
C# Trie代码
public class Solution {
public int LongestValidSubstring(string word, IList<string> forbidden) {
int n = word.Length;
Trie trie = new Trie();
foreach (var s in forbidden){
trie.Insert(s);
}
int j = 0, result = 0;
for (int i = 0; i < n; i++){
while (trie.Search(word, j, i)) j++;
result = Math.Max(result, i - j + 1);
}
return result;
}
}
public class Trie{
public TrieNode root;
public Trie(){
this.root = new TrieNode();
}
public void Insert(string s){
int n = s.Length;
TrieNode node = root;
for (int i = n - 1; i >= 0; i--){
int c = s[i] - 'a';
if (node.children[c] == null) node.children[c] = new TrieNode();
node = node.children[c];
}
node.isWord = true;
}
public bool Search(string s, int left, int right){
int t = Math.Max(left, right - 10);
for (int i = right; i >= t; i--){
TrieNode node = root;
for (int j = i; j >= t; j--){
int c = s[j] - 'a';
if (node.children[c] == null) break;
node = node.children[c];
if (node.isWord) return true;
}
}
return false;
}
}
public class TrieNode{
public TrieNode[] children;
public bool isWord;
public TrieNode(){
this.children = new TrieNode[26];
}
}