-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTrieST.php
More file actions
61 lines (54 loc) · 1.22 KB
/
TrieST.php
File metadata and controls
61 lines (54 loc) · 1.22 KB
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
61
<?php
/**
* 单词查找树算法
*/
class TrieST
{
private $_root=null;
/**
*查找单词$key
*
*/
public function search(string $key){
$node=$this->_search($this->_root,$key,0);
if(is_null($node)){
return null;
}
return $node->getVal();
}
private function _search($node,string $key,int $keyIndex){
if(is_null($node)){
return null;
}
if(strlen($key)==$keyIndex){
return $node;
}
$nextNodePos=$key[$keyIndex];
return $this->_search($node->getNextNode($nextNodePos),$key,++$keyIndex);
}
/**
* 添加单词
* @param string key 要添加的单词
*/
public function put(string $key,$value){
if(is_null($this->_root)){
$this->_root=$this->_put($this->_root,$key,$value,0);
}
$this->_put($this->_root,$key,$value,0);
}
private function _put($node,string $key,$value,int $keyIndex){
if(is_null($node)){
$node=new Node();
}
if(strlen($key)==$keyIndex){
$node->setVal($value);
return $node;
}
$nextNodePos=$key[$keyIndex];
$nextNode=$this->_put($node->getNextNode($nextNodePos),$key,$value,++$keyIndex);
$node->setNextNode($nextNodePos,$nextNode);
return $node;
}
public function keyWithPrefix(string $pre){
}
}