算法基本型——前缀树

引言

1. 前缀树

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

LeetCode 208. 实现 Trie (前缀树)，该题可以帮助我们很好的了解前缀树的概念以及应用。

下面这篇入门通俗易懂。

https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/trie-tree-de-shi-xian-gua-he-chu-xue-zhe-by-huwt/

2. 前缀树基本型

那么入门后，我们直接给出前缀树的基本型：

type Trie struct {
    isEnd bool
    next  [26]*Trie
}


func Constructor() Trie {
    return Trie{}
}


func (this *Trie) Insert(word string)  {
    node := this
    for _, c := range word {
        if node.next[c-'a'] == nil {
            node.next[c-'a'] = &Trie{}
        }
        node = node.next[c-'a']
    }
    node.isEnd = true
}


func (this *Trie) Search(word string) bool {
    node := this
    for _, c := range word {
        if node.next[c-'a'] == nil {
            return false
        }
        node = node.next[c-'a']
    }
    return node.isEnd == true
}


func (this *Trie) StartsWith(prefix string) bool {
    node := this
    for _, c := range prefix {
        if node.next[c-'a'] == nil {
            return false
        }
        node = node.next[c-'a']
    }
    return true
}

首先前缀树适合字符串的搜索，搜索字符会出现分支，就像一棵多叉树一样。

3. 基本型的应用

LeetCode 212. 单词搜索 II

一般字符串搜索可能就用到前缀树，形式比较固定。

我们直接给出题解：

type Trie struct {
    word  string   // 用于记录单词，会用到
    next  [26]*Trie
}

func (this *Trie) Insert(word string)  {
    node := this
    for _, c := range word {
        if node.next[c-'a'] == nil {
            node.next[c-'a'] = &Trie{}
        }
        node = node.next[c-'a']
    }
    node.word = word
}

var dirs = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func findWords(board [][]byte, words []string) []string {
    t := &Trie{}
    for _, word := range words {
        t.Insert(word)
    }

    seen := map[string]bool{}
    for i, row := range board {
        for j := range row {
            dfs(board, seen, t, i, j)
        }
    }
    ans := make([]string, 0, len(seen))
    for s := range seen {
        ans = append(ans, s)
    }
    return ans
}

func dfs(board [][]byte, seen map[string]bool, node *Trie, x, y int) {
    ch := board[x][y]
    node = node.next[ch-'a']
    if node == nil {
        return
    }

    if node.word != "" {
        seen[node.word] = true
    }

    board[x][y] = '#'
    for _, dir := range dirs {
        nx, ny := x+dir.x, y+dir.y
        if 0 <= nx && nx < len(board) && 0 <= ny && ny < len(board[0]) && board[nx][ny] != '#' {
            dfs(board, seen, node, nx, ny)
        }
    }
    board[x][y] = ch
}