php前缀树

这里先放代码演示，记录一下

class TrieNode {
    public $children = [];
    public $isEndOfWord = false;
}

class Trie {
    private $root;

    public function __construct() {
        $this->root = new TrieNode();
    }

    public function insert($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $char = $word[$i];
            if (!isset($node->children[$char])) {
                $node->children[$char] = new TrieNode();
            }
            $node = $node->children[$char];
        }
        $node->isEndOfWord = true;
    }

    public function search($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $char = $word[$i];
            if (!isset($node->children[$char])) {
                return false;
            }
            $node = $node->children[$char];
        }
        return $node->isEndOfWord;
    }

    public function startsWith($prefix) {
        $node = $this->root;
        for ($i = 0; $i < strlen($prefix); $i++) {
            $char = $prefix[$i];
            if (!isset($node->children[$char])) {
                return false;
            }
            $node = $node->children[$char];
        }
        return true;
    }
}

// 使用示例
$trie = new Trie();
$trie->insert("apple");
echo $trie->search("apple") ? "Found" : "Not Found"; // 输出: Found
echo $trie->search("app") ? "Found" : "Not Found";   // 输出: Not Found
echo $trie->startsWith("app") ? "Yes" : "No";        // 输出: Yes
$trie->insert("app");
echo $trie->search("app") ? "Found" : "Not Found";   // 输出: Found

编辑:

阅读量:115

url链接:https://www.qozr.com/cms_php-qian-zhui-shu.html

Tag标签: php