数据结构与算法——字典树
本文最后更新于 578 天前,其中的信息可能已经有所发展或是发生改变。

字典树

字典树(Trie) 又称单词查找树或键树,是一种哈希树的变种。典型的应用是用于统计和排序大量的字符串(但不限于字符串),优点是可以可以最大限度地减少无畏的字符串比较,查询效率比哈希表高。Trie的核心思想是空间换时间,利用字符串的公共前缀来降低查询的时间。

比如有一个包含多个单词的列表:[‘word’, ‘work’, ‘code’, ‘coffe’],可以下面的字典树表示:

字典树的性质:

  • 根节点不包含字符,除根节点外每个节点只包含一个字符
  • 从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串
  • 每个节点的所有子节点包含的字符串都不同

从头实现字符串(leetcode第208题):实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。示例:

Trie trie = new Trie(); 
trie.insert(apple);
trie.search(apple);   // 返回 true
trie.search(app);     // 返回 false
trie.startsWith(app); // 返回 true
trie.insert(app);   
trie.search(app);     // 返回 true

说明:你可以假设所有的输入都是由小写字母 a-z 构成的;保证所有输入均为非空字符串。

class Trie:
    def __init__(self):

        Initialize your data structure here.

        self.root = {}
        self.end_of_word = '#'

    def insert(self, word: str) -> None:

        Inserts a word into the trie.

        node = self.root
        for c in word:
            node = node.setdefault(c, {})
        node[self.end_of_word] = 1

    def search(self, word: str) -> bool:

        Returns if the word is in the trie.

        node = self.root
        for c in word:
            if c not in node:
                return False
            node = node[c]
        return self.end_of_word in node

    def startsWith(self, prefix: str) -> bool:

        Returns if there is any word in the trie that starts with the given prefix.

        node = self.root
        for c in prefix:
            if c not in node:
                return False
            node = node[c]
        return True

上面是比较造轮子的一种方法,而在python里可以直接用字典来实现字典树

例题

单词搜索II

此题为leetcode第212题给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

思路:字典树+深度优先搜索

# 方向数组
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# word结束标记
end_of_word = '#'

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        if not board or len(board[0]) == 0 or len(words) == 0:
            return []

        self.res = set()    # 结果保存在集合中
        root = {}   # 初始化根节点为空字典
        # 对列表里的word构建字典树
        for word in words:
            node = root
            # 这里的root将会是一个字典层层嵌套的结构。
            # 如果c在node里,则取出键为c的值,如果不在,则在键c下新建空字典
            for c in word:
                node = node.setdefault(c, {})   
            node[end_of_word] = end_of_word     # 标记word已结束

        self.m, self.n = len(board), len(board[0])

        # 遍历board,进行DFS
        for i in range(self.m):
            for j in range(self.n):
                if board[i][j] in root:
                    self._dfs(board, i, j, '', root)

        return list(self.res)

    def _dfs(self, board, i, j, curr_word, curr_dict):
        curr_word += board[i][j]
        curr_dict = curr_dict[board[i][j]]

        if end_of_word in curr_dict:
            self.res.add(curr_word)

        temp, board[i][j] = board[i][j], '*'    # '*'表示暂时标记为已访问过
        # 在(i, j)的4个方向上遍历
        for k in range(4):
            x, y = i + dx[k], j + dy[k]
            # 如果x、y没有越界,并且没有被访问过,并且当前字母在curr_dict中
            if 0 <= x < self.m and 0 <= y < self.n and board[x][y] != '*' and board[x][y] in curr_dict:
                self._dfs(board, x, y, curr_word, curr_dict)
        board[i][j] = temp  # 恢复board[i][j]的值
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇