@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: Trie implements the Collection interface.

  • set(element: Readonly<E>, value: V, start?: number, end?: number): this: Insert a string (or an array) into the trie.

  • delete(element: Readonly<E>, start?: number, end?: number): boolean: Remove a string (or an array) from the trie.

  • get(element: Readonly<E>, start?: number, end?: number): V | undefined: Find the value of the element which exactly matched the element.slice(start, end). If there is no such an element, then return undefined.

  • has(element: Readonly<E>, start?: number, end?: number): boolean: Check if there is an element exactly matched the element.slice(start, end).

  • hasPrefix(prefix: Readonly<E>, start?: number, end?: number): boolean: Check if there is an element which prefix matched the prefix.slice(start, end).

  • find(element: Readonly<E>, start?: number, end?: number): ITrieNodeData<V> | undefined: Find word with smallest length in the trie which exact match the element.slice(start, x), where the x is an integer in the range [start, _end).

  • findAll(element: Readonly<E>, start?: number, end?: number): Iterable<ITrieNodeData<V>>: Find all words in the trie which exact match the element.slice(start, x), where the x is an integer in the range [start, _end).

• Util

  • digitIdx(c: string): number: Calc idx of digit character.
  • uppercaseIdx(c: string): number: Calc idx of uppercase English letter.
  • lowercaseIdx(c: string): number: Calc idx of lowercase English letter.
  • alphaNumericIdx(c: string): number: Calc idx of digit, lowercase/uppercase English leter.

Example

• A solution of https://leetcode.com/problems/word-break-ii/:

  import type { ITrie } from '@algorithm.ts/trie'
  import { Trie, lowercaseIdx } from '@algorithm.ts/trie'
  
  const trie: ITrie<string, number> = new Trie<string, number>({
    SIGMA_SIZE: 26,
    idx: lowercaseIdx,
    mergeNodeValue: (_x, y) => y,
  })
  
  export function wordBreak(text: string, wordDict: string[]): string[] {
    if (text.length <= 0) return []
  
    trie.clear()
    for (let i = 0; i < wordDict.length; ++i) {
      const word = wordDict[i]
      trie.set(word, i)
    }
  
    const N = text.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])
            .join(' '),
        )
        return
      }
  
      for (const { end, val } of trie.findAll(text, pos, text.length)) {
        collect[cur] = val
        dfs(cur + 1, end)
      }
    }
  }
  

• A solution of https://leetcode.com/problems/word-search-ii/

  import { Trie, lowercaseIdx } from '@algorithm.ts/trie'
  
  class CustomTrie<E extends unknown[] | string, V> extends Trie<E, V> {
    public getSnapshot(): { ch: Uint32Array[]; values: Array<V | undefined> } {
      return {
        ch: this._ch,
        values: this._values,
      }
    }
  }
  
  const trie = new CustomTrie<string, number>({
    SIGMA_SIZE: 26,
    idx: lowercaseIdx,
    mergeNodeValue: (x, _y) => x,
  })
  
  export function findWords(board: string[][], words: string[]): string[] {
    const N = words.length
    const R = board.length
    const C = board[0].length
    if (N <= 0 || R <= 0 || C <= 0) return []
  
    trie.clear()
    for (let i = 0; i < N; ++i) trie.set(words[i], i)
  
    const boardCode: number[][] = []
    for (let r = 0; r < R; ++r) {
      const codes: number[] = []
      for (let c = 0; c < C; ++c) codes[c] = board[r][c].charCodeAt(0) - 97
      boardCode[r] = codes
    }
  
    const visited: boolean[][] = new Array(R)
    for (let r = 0; r < R; ++r) visited[r] = new Array(C).fill(false)
  
    let matchedWordCount = 0
    const isWordMatched: boolean[] = new Array(N).fill(false)
  
    const { ch, values } = trie.getSnapshot()
    for (let r = 0; r < R; ++r) {
      for (let c = 0; c < C; ++c) {
        dfs(0, r, c)
      }
    }
  
    const results: string[] = words.filter((_w, i) => isWordMatched[i])
    return results
  
    function dfs(u: number, r: number, c: number): void {
      if (visited[r][c] || matchedWordCount === N) return
  
      const u2: number = ch[u][boardCode[r][c]]
      if (u2 === 0) return
  
      const val = values[u2]
      if (val !== undefined && !isWordMatched[val]) {
        isWordMatched[val] = true
        matchedWordCount += 1
      }
  
      visited[r][c] = true
      if (r > 0) dfs(u2, r - 1, c)
      if (c + 1 < C) dfs(u2, r, c + 1)
      if (r + 1 < R) dfs(u2, r + 1, c)
      if (c > 0) dfs(u2, r, c - 1)
      visited[r][c] = false
    }
  }
  

Related

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