LC 1065 [E] Index Pairs of a String - ALawliet/algorithms GitHub Wiki

class TrieNode:
    def __init__(self):
        self.children, self.is_word = {}, False

    @staticmethod
    def construct_trie(words):
        root = TrieNode()
        for word in words:
            node = root
            for c in word:
                node.children.setdefault(c, TrieNode())
                node = node.children[c]
            node.is_word = True
        return root

class Solution:
    def indexPairs(self, text, words):
        res, trie = [], TrieNode.construct_trie(words)
        for l in range(len(text)):
            node = trie
            for r in range(l, len(text)):
                if text[r] not in node.children:
                    break
                node = node.children[text[r]]
                if node.is_word:
                    res.append((l, r))
        return res

class TrieNode:
  def __init__(self):
    self.children = {}
    self.endWord = False

class Trie:
  def __init__(self):
    self.root = TrieNode()
  
  def insert(self, word):
    cur = self.root
    for c in word:
      if c not in cur.children:
        cur.children[c] = TrieNode()
      cur = cur.children[c]
    cur.endWord = True
  
  def contains(self, root, letter):
    return letter in root.children
    
class Solution:
  def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:
    a = Trie()
    
    for word in words:
      a.insert(word)
    
    res = []
    
    for i in range(len(text)):
      j = i
      cur = a.root
      
      while j < len(text) and a.contains(cur, text[j]):
        cur = cur.children[text[j]]
        j += 1
        
        if cur.endWord:
          res.append([i, j-1])
        
    return res

Let n = len(text), m = len(words), k = maximal length of each word in words.

Solution 1: time complexity O(n * m * k) + O(m log m) (Beat 93.62%)

    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:
        res = []
        n = len(text)
        for i in range(n):
            for w in words:
                j = i + len(w) - 1
                if j < n and text[i:j+1] == w:
                    res.append([i, j])
        res.sort()
        return res

Solution 2: Trie search, time complexity: build a trie O(m *k), search in the trie O(n * k) (Beat 58.66%)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEnd = True

class Solution:
    def indexPairs(self, text, words):
        trie = Trie()

        for word in words:
            trie.insert(word)

        res = []
        n = len(text)
        for i in range(n):
            j = i
            node = trie.root
            while j < n and text[j] in node.children:
                node = node.children[text[j]]
                if node.isEnd:
                    res.append([i, j])
                j += 1
        return res