1065-index-pairs-of-a-string.js

/**
 * @param {string} text
 * @param {string[]} words
 * @return {number[][]}
 */
const indexPairs = function(text, words) {
  const res = [], trie = buildTrie(words)
  const n = text.length
  for(let i = 0; i < n; i++) {
    let node = trie
    for(let j = i; j < n; j++) {
      if(node.children[text[j]] == null) break
      node = node.children[text[j]]
      if(node.isWord) res.push([i, j])
    }
  }

  return res
};

function buildTrie(words) {
  const root = new Trie()
  
  for(let word of words) {
    let node = root
    for(let c of word) {
      if(node.children[c] == null) node.children[c] = new Trie()
      node = node.children[c]
    }
    node.isWord = true
  }

  return root
}

class Trie {
  constructor() {
    this.children = {}
    this.isWord = false
  }
}