1065. Index Pairs of a String

https://leetcode.com/problems/index-pairs-of-a-string/

Python

• Time: O(NlogN) # N = len(text)
• Space: O(K) # K = sum(len(words))

class Solution:
    EOS = '-'
    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:
        # Build the Tire search tree for all words
        root = {}
        for word in words:
            cur = root
            for letter in word:
                cur = cur.setdefault(letter, {})
            cur[self.EOS] = True

        result = []
        for i in range(len(text)):
            cur = root
            for j in range(i, len(text)):
                if text[j] not in cur:
                    break
                cur = cur[text[j]]
                if self.EOS in cur:
                    result.append([i, j])

        return result

Javascript

var indexPairs = function (text, words) {
	const trie = new Trie();
	trie.insert(words);
	return trie.find(text);
};

class Trie {
	constructor() {
		this.root = {};
	}

	insert(words) {
		for (const word of words) {
			let node = this.root;
			for (const char of word) {
				if (!node[char]) node[char] = {};
				node = node[char];
			}
			node.isMatched = true;
		}
	}

	find(text) {
		const result = [];

		outer: 
        for (let i = 0; i < text.length; i++) {
			let node = this.root;
			for (let k = i; k < text.length; k++) {
				const char = text[k];

				if (!node[char]) continue outer;
				else if (node[char].isMatched) {
					result.push([i, k]);
				}
				node = node[char];
			}
		}
		return result;
	}
}