给你一个字符串数组 words 和一个字符串 pref 。
返回 words 中以 pref 作为 前缀 的字符串的数目。
字符串 s 的 前缀 就是 s 的任一前导连续字符串。
示例 1：
输入：words = [“pay”,“attention”,“practice”,“attend”], pref = “at”
输出：2
解释：以 “at” 作为前缀的字符串有两个，分别是：“attention” 和 “attend” 。
示例 2：
输入：words = [“leetcode”,“win”,“loops”,“success”], pref = “code”
输出：0
解释：不存在以 “code” 作为前缀的字符串。
提示：
1 <= words.length <= 100
1 <= words[i].length, pref.length <= 100
words[i] 和 pref 由小写英文字母组成
public int prefixCount(String[] words, String pref) {
int result=0;
for (String word : words) {
Trie node=new Trie();
node.insert(word,pref.length());
if (node.startsWith(pref)){
result++;
}
}
return result;
}
public class Trie{
Trie[] children;
public Trie(){
children=new Trie[26];
}
public void insert(String word,int len){
Trie node=this;
for (int i = 0; i < word.length()&&i<len; i++) {
int index = word.charAt(i) - 'a';
if (node.children[index]==null){
node.children[index]=new Trie();
}
node=node.children[index];
}
}
public Boolean startsWith(String prefix){
Trie node=this;
for (int i = 0; i < prefix.length(); i++) {
int index = prefix.charAt(i) - 'a';
if (node.children[index]==null){
return false;
}
node=node.children[index];
}
return true;
}
}
func prefixCount(words []string, pref string) int {
result:=0
for _, v := range words {
node:=&Trie{
children:make([]*Trie,26),
}
node.insert(v, len(pref))
if node.startsWith(pref) {
result++
}
}
return result
}
type Trie struct {
children []*Trie
}
func (node *Trie)insert(word string, length int){
for i:=0;i<len(word)&&i<length;i++{
index:=word[i]-'a'
if node.children[index]==nil {
node.children[index]=&Trie{
children:make([]*Trie,26),
}
}
node=node.children[index]
}
}
func (node *Trie)startsWith(prefix string) bool {
for _, v := range prefix {
index:=v-'a'
if node.children[index]==nil {
return false
}
node=node.children[index]
}
return true
}
