@algorithm.ts/trie

@algorithm.ts/trie

A typescript implementation of the TRIE data structure.

The following definition is quoted from Wikipedia (https://en.wikipedia.org/wiki/Trie):

In computer science, a trie, also called digital tree or prefix tree, is a type of search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters. In order to access a key (to recover its value, change it, or remove it), the trie is traversed depth-first, following the links between nodes, which represent each character in the key.

Install

• npm

  npm install --save @algorithm.ts/trie
  

• yarn

  yarn add @algorithm.ts/trie
  

Usage

• Trie

  • init(): void: Initialize a trie.

  • insert(str: string, v: T, start?: number, end?: number): void: Insert a string into the trie.

  • match(str: string, start?: number, end?: number): T | null: Find a word in the trie which exact match the str.slice(start, end). If there is such a word, return its additional value, otherwise return null.

  • find(str: string, start?: number, end?: number): TrieNodeData<T> | null: Find word with smallest length in the trie which exact match the str.slice(start, x), where the x is an integer in the range [start, _end).

  • findAll(str: string, start?: number, end?: number): Array<TrieNodeData<T>>: Find all words in the trie which exact match the str.slice(start, x), where the x is an integer in the range [start, _end).

• Solve https://leetcode.com/problems/word-break-ii/:

  import { Trie, createTrie } from '@algorithm.ts/trie'
  
  const trie: Trie = createTrie({
    SIGMA_SIZE: 26,
    ZERO: 0,
    idx: (c: string): number => c.codePointAt(0)! - 97,
    mergeAdditionalValues: (x, y) => y,
  })
  
  export function wordBreak(s: string, wordDict: string[]): string[] {
    if (s.length <= 0) return []
  
    trie.init()
    for (let i = 0; i < wordDict.length; ++i) {
      const word = wordDict[i]
      trie.insert(word, i + 1)
    }
  
    const N = s.length
    const results: string[] = []
    const collect: number[] = []
    dfs(0, 0)
    return results
  
    function dfs(cur: number, pos: number): void {
      if (pos === N) {
        results.push(
          collect
            .slice(0, cur)
            .map(x => wordDict[x - 1])
            .join(' '),
        )
        return
      }
  
      const pairs = trie.findAll(s, pos)
      for (const { end, val } of pairs) {
        collect[cur] = val
        dfs(cur + 1, end)
      }
    }
  }
  

Related

• https://en.wikipedia.org/wiki/Trie