skip to content
WNLee's Blog

数据结构之单词树

/ 3 min read

数据结构, 单词树

单词树是从根节点到某个节点经过的节点可以组合成一个单词的树形结构...

单词树

概念

单词树是一种数据结构，是从根节点到某个节点经过的节点上的字母可以组合成一个单词的树形结构。

实现

class TreeNode extends Map {
  val: boolean = false;

  constructor(val: boolean) {
    super();
    this.val = val;
  }
}

class WordTree {
  root: TreeNode;
  constructor(sortList: string[]) {
    this.root = buildTree(undefined, sortList);
  }

  add(words: string[]) {
    buildTree(this.root, words);
  }
  addOne(word: string) {
    this.add([ word ]);
  }
}

function buildTree(root: TreeNode = new TreeNode(false), sortList: string[]): TreeNode {
  sortList.forEach(item => {
    let i = 0;
    let node = root;
    while(i < item.length) {
      const w = item.charAt(i);
      if (!node.has(w)) {
        node.set(w, new TreeNode(i === item.length - 1));
      }
      node = node.get(w);
      i++;
    }
  });
  return root;
}

特性

  1. 从根节点出发到某个值为true的节点，经过的节点上的字母可以组合成一个单词；

  2. 从根节点出发到叶子节点，经过的节点上的字母可以组合成一个单词；

单词搜索应用

给定一个单词数组，输入一个字符串可以匹配出补全的单词；如：单词组为 [translate, transform, animal]，输入”tr”可以补全出 [translate, transform];

一般情况下我们会这么做：

function sortWords(sortList: string[], prefix: string) {
  return sortList.filter(word => word.indexOf(prefix) === 0);
}

但是，假设是很大的数据量1000个单词，会导致比较大的运算，可以尝试使用单词树。

/**
 * WordTree
 */
class TreeNode extends Map {
  val: boolean = false;

  constructor(val: boolean) {
    super();
    this.val = val;
  }
}

class WordTree {
  root: TreeNode;
  constructor(sortList: string[]) {
    this.root = buildTree(undefined, sortList);
  }

  add(words: string[]) {
    buildTree(this.root, words);
  }
  addOne(word: string) {
    this.add([ word ]);
  }
}

function buildTree(root: TreeNode = new TreeNode(false), sortList: string[]): TreeNode {
  sortList.forEach(item => {
    let i = 0;
    let node = root;
    while(i < item.length) {
      const w = item.charAt(i);
      if (!node.has(w)) {
        node.set(w, new TreeNode(i === item.length - 1));
      }
      node = node.get(w);
      i++;
    }
  });
  return root;
}

/**
 * readline
 */
function findNode(root: TreeNode, search: string): TreeNode | false {
  let i = 0;
  let cache = root;

  while(i < search.length) {
    const l = search.charAt(i);
    if (!cache.has(l)) {
      return false;
    }
    cache = cache.get(l);
    i++;
  };

  return cache;
}

function sortWordFactory() {
  const result: string[] = [];
  return function sortWord(node: TreeNode, prefix: string) {
    if (node.val) {
      result.push(prefix);
    }

    for (let key of node.keys()) {
      sortWord(node.get(key), prefix + key);
    }

    return result;
  }
}

class Readline extends WordTree {
  constructor(sortList: string[]) {
    super(sortList);
  }

  sort(search: string) {
    const cache = findNode(this.root, search);

    if (!cache) return [];

    return sortWordFactory()(cache, search);
  }
}

输出结果： 1