[LeetCode] 2781. Length of the Longest Valid Substring

https://leetcode.com/problems/length-of-the-longest-valid-substring/description/

 

The main idea is to use Trie data structure.

 

1. Python

class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
        ret = 0
        trie = {}
        for f in forbidden:
            f = f[::-1]
            t = trie
            for c in f:
                if c not in t:
                    t[c] = {}
                t = t[c]
            t['#'] = len(f)
        j = 0
        for i in range(len(word)):
            valid = True
            nxtJ = None
            t = trie
            for k in range(i, j - 1, -1):
                c = word[k]
                if c not in t:
                    break
                t = t[c]
                if '#' in t:
                    valid = False
                    nxtJ = i - t['#'] + 2
                    break
            if valid is True:
                ret = max(ret, i - j + 1)
            else:
                j = nxtJ
        return ret

 

2. C++

class TrieNode {
	public:
		char ch;
		bool isWord;
		int length;
		TrieNode* children[26] {nullptr};
		
		TrieNode() {}
		
		TrieNode(char ch, bool isWord=false, int length=0): ch(ch), isWord(isWord), length(length) {}
		
		~TrieNode() {}
};


class Trie {
	public:
		TrieNode* root = new TrieNode();
		
		Trie () {}
		
		void insert(string word) {
			TrieNode* cur = root;
			for (char c : word) {
				int idx = c - 'a';
				if (cur->children[idx] == nullptr) {
					cur->children[idx] = new TrieNode(c);
				}
				cur = cur->children[idx];
			}
			cur->isWord = true;
			cur->length = word.size();
		}
		
		~Trie() {
			delete root;
		}		
};


class Solution {
public:
    int longestValidSubstring(string word, vector<string>& forbidden) {
        int ret = 0;
		Trie trie = Trie();
		for (string& word : forbidden) {
            reverse(word.begin(), word.end());
			trie.insert(word);
		}
		int j = 0;
		for (int i=0; i<word.size(); i++) {
			bool valid = true;
			int nxtJ = -1;
			TrieNode node = *trie.root;
			for (int k=i; k>j-1; k--) {
				char c = word[k];
				int idx = c - 'a';
				if (node.children[idx] == nullptr) {
					break;
				}
				node = *node.children[idx];
				if (node.isWord) {
					valid = false;
					nxtJ = i - node.length + 2;
					break;
				}
			}
			if (valid) {
				ret = max(ret, i - j + 1);
			} else {
				j = nxtJ;
			}
		}
		return ret;
    }
};