leetcode-php/src/leetcode/ImplementTriePrefixTree.php at master · imajinyun/leetcode-php · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
<?php

declare(strict_types=1);

namespace leetcode;

use leetcode\util\TrieNode;

class ImplementTriePrefixTree
{
    /** @var \leetcode\util\TrieNode */
    private $root;

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

    public function insert(string $word): void
    {
        /** @var \leetcode\util\TrieNode $node */
        $node = $this->root;
        for ($i = 0, $n = strlen($word); $i < $n; $i++) {
            $value = $word[$i];
            if (!isset($node->children[$value])) {
                $node->children[$value] = new TrieNode($value);
            }
            $node = $node->children[$value];
        }
        $node->isWord = true;
    }

    public function search(string $prefix): bool
    {
        $node = $this->root;
        for ($i = 0, $n = strlen($prefix); $i < $n; $i++) {
            $value = $prefix[$i];
            if (!isset($node->children[$value])) {
                return false;
            }
            $node = $node->children[$value];
        }

        return $node->isWord;
    }

    public function startsWith(string $prefix): bool
    {
        $node = $this->root;
        for ($i = 0, $n = strlen($prefix); $i < $n; $i++) {
            $value = $prefix[$i];
            if (!isset($node->children[$value])) {
                return false;
            }
            $node = $node->children[$value];
        }

        return true;
    }
}