trie树 PHP实现

我不是女神ヾ 2023-02-20 12:26 31阅读 0赞

Tire主要包含两个操作，一个是将字符串集合构造成 Trie 树。这个过程分解开来的话，就是一个将字符串插入到 Trie 树的过程。另一个是在 Trie 树中查询一个字符串。

Trie 树是个多叉树，在这里用数组来存储一个节点的所有子结点。

Trie树节点类，PHP代码实现：

<?php
    
     class TrieNode
    { 
         public $data;
         public $children = [];
         public $isEndingChar = false;
     
         public function __construct($data)
         { 
             $this->data = $data;
         }
     }

Trie树

<?php
    
    class Trie { 
        private $root;
    
        public function __construct() { 
            $this->root = new TrieNode('/'); //根节点
        }
    
        public function getRoot() { 
            return $this->root;
        }
    
        public function insert($text) { 
            $p = $this->root;
            for ($i = 0; $i < mb_strlen($text); $i++) { 
                $index = $data = $text[$i];
    
                if (empty($p->children[$index])) { 
                    $newNode = new TrieNode($data);
                    $p->children[$index] = $newNode;
                }
                $p = $p->children[$index];
            }
            $p->isEndingChar = true;
        }
    
        public function find($pattern) { 
            $p = $this->root;
            for ($i = 0; $i < mb_strlen($pattern); $i++) { 
                $index  = $pattern[$i];
    
                if (empty($p->children[$index])) { 
                    return false;
                }
                $p = $p->children[$index];
            }
    
    		return $p->isEndingChar;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，31人围观）

还没有评论，来说两句吧...

相关阅读

相关 208. 实现 Trie (前缀树)

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

旧城等待，/ 2024年05月08日 06:22/ 0 赞/ 136 阅读

相关 trie树 PHP实现

Tire主要包含两个操作，一个是将字符串集合构造成 Trie 树。这个过程分解开来的话，就是一个将字符串插入到 Trie 树的过程。另一个是在 Trie 树中查询一个字符串。

我不是女神ヾ/ 2023年02月20日 12:26/ 0 赞/ 32 阅读

相关 Trie树java实现

Trie树又称前缀树或称字典树，是一个多叉树。可以实现前缀匹配查询或者字符串匹配查询。以下是java实现版 imp

阳光穿透心脏的1/2处/ 2022年12月24日 13:55/ 0 赞/ 126 阅读

相关 Implement Trie (Prefix Tree) - 实现 Trie (前缀树 - 字典树)

Implement Trie (Prefix Tree) - 实现 Trie (前缀树 - 字典树) [https://leetcode-cn.com/problems/

待我称王封你为后i/ 2022年10月19日 00:56/ 0 赞/ 270 阅读

相关 LeetCode：208. Implement Trie (实现Trie树)

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

悠悠/ 2022年10月16日 07:12/ 0 赞/ 248 阅读

相关 208. 实现 Trie (前缀树)

> 请你实现 Trie 类： > > Trie() 初始化前缀树对象。 > void insert(String word) 向前缀树中插入字符串 word 。 >

- 日理万妓/ 2022年10月12日 12:09/ 0 赞/ 232 阅读

相关 trie字典树实现

实现了一个简单的字典树. 假设所有的字符只有26个小写字母，并且除了节点出现的次数之外还增加了类似map功能的索引。假如不只有26个字母，需要相应的做一些修改。

一时失言乱红尘/ 2022年09月27日 15:22/ 0 赞/ 243 阅读

相关 PHP实现Trie树（字典树）

Trie树的概念（百度的解释）：字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被

╰半橙微兮°/ 2022年09月21日 04:59/ 0 赞/ 231 阅读

相关 trie树(字典树)java实现

public class Trie{ private Node root; public Trie(){

àì夳堔傛蜴生んèń/ 2022年08月21日 15:00/ 0 赞/ 292 阅读

相关 python 实现 trie(字典) 树

`tire 树也叫字典树，也是一种 N 叉树，是一种特殊的前缀树结构。` `1、前缀树`是`N叉树`的一种特殊形式。通常来说，一个前缀树是用来`存储字符串`的。前缀树的每一

青旅半醒/ 2022年05月21日 06:23/ 0 赞/ 271 阅读