azl397985856 commented 2 years ago

实现 Trie (前缀树

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/implement-trie-prefix-tree

前置知识

树
Trie
题目描述

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple"); trie.search("apple"); // 返回 true trie.search("app"); // 返回 false trie.startsWith("app"); // 返回 true1 trie.insert("app"); trie.search("app"); // 返回 true 说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。保证所有输入均为非空字符串。

djd28176 commented 2 years ago


class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    public void insert(String word) {
        TrieNode node = root;
        for(int i = 0; i < word.length();i++){
            char currentChar = word.charAt(i);
            if(!node.containsKey(currentChar)){
                node.put(currentChar, new TrieNode());
            }
            node = node.get(currentChar);
        }
        node.setEnd();
    }
    private TrieNode searchPrefix(String word){
        TrieNode node = root;
        for(int i = 0; i < word.length(); i++){
            char curLetter = word.charAt(i);
            if(node.containsKey(curLetter)){
                node = node.get(curLetter);
            }else{
                return null;
            }
        }
        return node;
    }

    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd();
    }

    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }
}
class TrieNode {

    // R links to node children
    private TrieNode[] links;

    private final int R = 26;

    private boolean isEnd;

    public TrieNode() {
        links = new TrieNode[R];
    }

    public boolean containsKey(char ch) {
        return links[ch -'a'] != null;
    }
    public TrieNode get(char ch) {
        return links[ch -'a'];
    }
    public void put(char ch, TrieNode node) {
        links[ch -'a'] = node;
    }
    public void setEnd() {
        isEnd = true;
    }
    public boolean isEnd() {
        return isEnd;
    }
}

Yongxi-Zhou commented 2 years ago

思路

Tries

代码

    class Trie(object):

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        """
        :type word: str
        :rtype: None
        """
        cur = self.root
        for char in word:
            if cur.children[ord(char) - ord("a")] == None:
                cur.children[ord(char) - ord("a")] = TrieNode()
            cur = cur.children[ord(char) - ord("a")]
        cur.isWord = True

    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        cur = self.root
        for char in word:
            if cur.children[ord(char) - ord("a")] == None:
                return False
            cur = cur.children[ord(char) - ord("a")]
        return cur.isWord

    def startsWith(self, prefix):
        """
        :type prefix: str
        :rtype: bool
        """
        cur = self.root
        for char in prefix:
            if cur.children[ord(char) - ord("a")] == None:
                return False
            cur = cur.children[ord(char) - ord("a")]
        return True

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.isWord = False

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

复杂度

time O(n) space O(1)

MichaelXi3 commented 2 years ago

Idea

Prefix Tree

Code

class Trie {

    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            // If current node doesn't have this char as child
            if (cur.children[c - 'a'] == null) {
                cur.children[c - 'a'] = new TrieNode(c);
                cur = cur.children[c - 'a'];
            } else {
                cur = cur.children[c - 'a'];
            }
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (cur.children[c - 'a'] == null) {
                return false;
            }
            cur = cur.children[c - 'a'];
        }
        if (cur.isEnd) {
            return true;
        } else {
            return false;
        }
    }

    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (char c : prefix.toCharArray()) {
            if (cur.children[c - 'a'] == null) {
                return false;
            }
            cur = cur.children[c - 'a'];
        }
        return true;
    }
}

public class TrieNode {
    public  TrieNode[] children;
    public Boolean isEnd;
    public char value;

    public TrieNode() {
        this.children = new TrieNode[26];
    }

    public TrieNode(char val) {
        this.children = new TrieNode[26];
        this.isEnd = false;
        this.value = val;
    }
}

houmk1212 commented 2 years ago

class Trie {
    TrieNode root = null;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
            node.preCount++;
        }
        node.count++;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null) {
                return false;
            } else {
                node = node.children[c - 'a'];
            }
        }
        return node.count > 0;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (node.children[c - 'a'] == null) {
                return false;
            } else {
                node = node.children[c - 'a'];
            }
        }
        return node.preCount > 0;
    }
}

class TrieNode {
    int count;
    int preCount;
    TrieNode[] children = new TrieNode[26];

    public TrieNode() {
    }
}

xingchen77 commented 2 years ago

class TrieNode:
    def __init__(self):
        self.isEnd = False
        self.children = {}

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                node = TrieNode()
                cur.children[ch] = node
            cur = cur.children[ch]
        cur.isEnd = True

    def search(self, word: str) -> bool:
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        if cur.isEnd == True:
            return True
        return False

    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for ch in prefix:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return True 

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

carterrr commented 2 years ago

class Trie { Trie[] root; boolean isLeaf = false; public Trie() { root = new Trie[26]; }

public void insert(String word) {
    Trie cur = this;
    for(int i = 0; i < word.length(); i++) {
        int c = word.charAt(i) - 'a';
        Trie t = cur.root[c];
        if(t == null) {
            t = new Trie();
            cur.root[c] = t;
        }
        cur = t;
    }
    cur.isLeaf = true;
}

public boolean search(String word) {
    Trie cur = this;
    for(int i = 0; i < word.length(); i++) {
        int c = word.charAt(i) - 'a';
        Trie t = cur.root[c];
        if(t == null) return false;
        cur = t;
    }
    return cur.isLeaf;
}

public boolean startsWith(String prefix) {
    Trie cur = this;
    for(int i = 0; i < prefix.length(); i++) {
        int c = prefix.charAt(i) - 'a';
        Trie t = cur.root[c];
        if(t == null) return false;
        cur = t;
    }
    return true;
}

}

/**

Your Trie object will be instantiated and called as such:
Trie obj = new Trie();
obj.insert(word);
boolean param_2 = obj.search(word);
boolean param_3 = obj.startsWith(prefix); */

MoonLee001 commented 2 years ago

var Trie = function() {
    this.children = {};
};

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let node = this.children;
    for (let ch of word) { 
        if (!node[ch]) {
            node[ch] = {};
        }
        node = node[ch];
    }
    node.isEnd = true;
};

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let node = this.children;
    for (let ch of word) {
        if (!node[ch]) {
            return false;
        }
        node = node[ch];
    }
    return node.isEnd ? true : false;
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let node = this.children;
    for (let ch of prefix) {
        if (!node[ch]) {
            return false;
        }
        node = node[ch];
    }
    return true;
};

currybeefer commented 2 years ago

class TrieNode { public: TrieNode *child[26]; bool isWord; // 初始化 TrieNode(): isWord(false){ for (auto &c: child) c = nullptr; } };

class Trie { private: TrieNode* root;

public: /* Initialize your data structure here. / Trie() { root = new TrieNode(); }

/** Inserts a word into the trie. */
void insert(string word) {
    TrieNode *p = root;

    for (auto a: word) {
        int index = a - 'a';
        if (!p->child[index]) p->child[index] = new TrieNode();
        p = p->child[index];
    }
    p->isWord = true;
}

/** Returns if the word is in the trie. */
bool search(string word) {
    TrieNode *p = root;

    for (auto a: word) {
        int index = a - 'a';
        if (!p->child[index]) return false;
        p = p->child[index];
    }
    return p->isWord;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
    TrieNode *p = root;
    for (auto a : prefix) {
        int index = a - 'a';
        if (!p->child[index]) return false;
        p = p->child[index];
    }
    return true;
}

};

wenliangchen commented 2 years ago

Idea

HashMap

code

class Trie {

    class TrieNode{
        public TrieNode(){
            children = new HashMap<>();
            isWord = false;
        }
        public boolean isWord;
        HashMap<Character,TrieNode> children;
    }
    private TrieNode root;

    public Trie() {
        root = new TrieNode();

    }

    public void insert(String word) {
        TrieNode p = root;
        for(int i = 0; i < word.length();i++){
            char index = word.charAt(i);
            if(p.children.get(index) == null){
                p.children.put( index, new TrieNode());
            }
            p = p.children.get(index);
        }
        p.isWord = true;
    }

    public boolean search(String word) {
        TrieNode p = root;
        for(int i = 0; i < word.length();i++){
            char index = word.charAt(i);
            if(p.children.get(index) == null){
                return false;
            }
            p = p.children.get(index);
        }
        return p.isWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode p = root;
        for(int i = 0; i < prefix.length();i++){
            char index = prefix.charAt(i) ;
            if(p.children.get(index) == null){
                return false;
            }
            p = p.children.get(index);
        }

        return true;
    }
}

HuiWang1020 commented 2 years ago

class Trie {
    class Node{
        Node[] children;
        boolean isWord;
        public Node() {
            children = new Node[26];
            isWord = false;
        }
    }

    Node root;
    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char cur = word.charAt(i);
            if (node.children[cur - 'a'] == null) {
                node.children[cur - 'a'] = new Node();    
            } 
            node = node.children[cur - 'a'];
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char cur = word.charAt(i);
            if (node.children[cur - 'a'] == null) {
                return false;    
            }
            node = node.children[cur - 'a'];
        }
        return node.isWord;
    }

    public boolean startsWith(String prefix) {
         Node node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char cur = prefix.charAt(i);
            if (node.children[cur - 'a'] == null) {
                return false;    
            }
            node = node.children[cur - 'a'];
        }
        return true;
    }
}

Jongeehsu commented 2 years ago

class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

zhiyuanpeng commented 2 years ago

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False

    def searchPrefix(self, prefix: str) -> "Trie":
        node = self
        for ch in prefix:
            ch = ord(ch) - ord("a")
            if not node.children[ch]:
                return None
            node = node.children[ch]
        return node

    def insert(self, word: str) -> None:
        node = self
        for ch in word:
            ch = ord(ch) - ord("a")
            if not node.children[ch]:
                node.children[ch] = Trie()
            node = node.children[ch]
        node.isEnd = True

    def search(self, word: str) -> bool:
        node = self.searchPrefix(word)
        return node is not None and node.isEnd

    def startsWith(self, prefix: str) -> bool:
        return self.searchPrefix(prefix) is not None

xil324 commented 2 years ago

class TrieNode: 
    def __init__(self): 
        self.children = {}; 
        self.isWord = False;

class Trie(object):

    def __init__(self):
        self.root = TrieNode(); 

    def insert(self, word):
        """
        :type word: str
        :rtype: None
        """
        node = self.root;
        for letter in word:
            if letter not in node.children:
                node.children[letter] = TrieNode();
            node = node.children[letter]; 
        node.isWord = True; 

    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        node = self.startsWith(word); 
        if node is not None and node.isWord:
            return True; 
        return False; 

    def startsWith(self, prefix):
        """
        :type prefix: str
        :rtype: bool
        """
        node = self.root; 
        for letter in prefix:
            node = node.children.get(letter)
            if node is None:
                return None; 
        return node;

fhuang5 commented 2 years ago

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if (!node.containsKey(currentChar)) {
                node.put(currentChar, new TrieNode());
            }
            node = node.get(currentChar);
        }
        node.setEnd();
    }

    // search a prefix or whole key in trie and
    // returns the node where search ends
    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
           char curLetter = word.charAt(i);
           if (node.containsKey(curLetter)) {
               node = node.get(curLetter);
           } else {
               return null;
           }
        }
        return node;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
       TrieNode node = searchPrefix(word);
       return node != null && node.isEnd();
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }
}

zenwangzy commented 2 years ago

class TrieNode { public: TrieNode *child[26]; bool isWord; // 初始化 TrieNode(): isWord(false){ for (auto &c: child) c = nullptr; } };

class Trie { private: TrieNode* root;

public: /* Initialize your data structure here. / Trie() { root = new TrieNode(); }

/* Inserts a word into the trie. / void insert(string word) { TrieNode *p = root;

for (auto a: word) {
    int index = a - 'a';
    if (!p->child[index]) p->child[index] = new TrieNode();
    p = p->child[index];
}
p->isWord = true;

}

/* Returns if the word is in the trie. / bool search(string word) { TrieNode *p = root;

for (auto a: word) {
    int index = a - 'a';
    if (!p->child[index]) return false;
    p = p->child[index];
}
return p->isWord;

}

/* Returns if there is any word in the trie that starts with the given prefix. / bool startsWith(string prefix) { TrieNode *p = root; for (auto a : prefix) { int index = a - 'a'; if (!p->child[index]) return false; p = p->child[index]; } return true; } };

hyh331 commented 2 years ago

Day73 思路

class Trie {
private:
    Trie* son[26];
    bool isEnd;
public:
    //构造函数，初始化，isEnd初始化为false，son初始化为nullptr
    Trie() {
        isEnd = false;
        for(int i=0; i<26; i++){
            son[i]=nullptr;
        }
    }
    ~Trie(){
        for(int i=0; i<26; i++){
            if(son[i] != nullptr) delete son[i];
        }
    }
    Trie* isPrefix(string word){
        Trie* root= this;
        for(auto &x : word){
            int cur = x-'a';
            if(root->son[cur] ==nullptr) return nullptr;
            root = root->son[cur]; 
        }
        return root;
    }
    void insert(string word) {
        Trie* root=this;
        //开始对插入进来的字符串进行遍历
        for(char x:word){
            int cur= x-'a';
            //若对应为空指针，则新建一个节点
            if(root->son[cur] == nullptr) root->son[cur] = new Trie();
            root = root->son[cur];
        }
        root-> isEnd =true;
    }

    bool search(string word) {
        return isPrefix(word) && isPrefix(word)->isEnd==true;
    }

    bool startsWith(string prefix) {
        return isPrefix(prefix);
    }
};

复杂度分析

时间复杂度：O(n),n为每次插入字符串的长度
空间复杂度：O(nk) 节点数量n，字符集大小为k

miss1 commented 2 years ago

代码


var Trie = function() {
  this.children = {};
  this.count = 0;
  this.preCount = 0;
};

/**
 * @param {string} word
 * @return {void}
 * time: O(len(word))
 */
Trie.prototype.insert = function(word) {
  let node = this.children;
  for (let char of word) {
    if (!node[char]) node[char] = { count: 0, preCount: 0};
    node = node[char];
    node.preCount += 1;
  }
  node.count += 1;
};

/**
 * @param {string} word
 * @return {boolean}
 * time: O(len(word))
 */
Trie.prototype.search = function(word) {
  let node = this.children;
  for (let char of word) {
    if (!node[char]) return false;
    node = node[char];
  }
  return node.count > 0;
};

/**
 * @param {string} prefix
 * @return {boolean}
 * time: O(len(prefix))
 */
Trie.prototype.startsWith = function(prefix) {
  let node = this.children;
  for (let char of prefix) {
    if (!node[char]) return false;
    node = node[char];
  }
  return node.preCount > 0;
};

wychmod commented 2 years ago

代码

class Trie:

    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False

    def insert(self, word: str) -> None:
        if not word:
            return
        node = self
        for i in word:
            ch = ord(i) - ord('a')
            if not node.children[ch]:
                node.children[ch] = Trie()
            node = node.children[ch]
        node.isEnd = True

    def search(self, word: str) -> bool:
        if not word:
            return
        node = self
        for i in word:
            ch = ord(i) - ord('a')
            if not node.children[ch]:
                return False
            node = node.children[ch]
        return node.isEnd

    def startsWith(self, prefix: str) -> bool:
        if not prefix:
            return
        node = self
        for i in prefix:
            ch = ord(i) - ord('a')
            if not node.children[ch]:
                return False
            node = node.children[ch]
        return True

shawnhu23 commented 2 years ago

Idea

trie

Code

class Trie {

    public TrieNode root;

    public static class TrieNode {
        public int pass;
        public int end;
        public TrieNode[] nexts;

        public TrieNode() {
            pass = 0;
            end = 0;
            nexts = new TrieNode[26];
        }    
    }

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        char[] chs = word.toCharArray();
        TrieNode t = this.root;
        int index = 0;
        for (int i = 0; i < chs.length; i++) {
            index = chs[i] - 'a';
            if (t.nexts[index] == null) {
                t.nexts[index] = new TrieNode();
            }
            t = t.nexts[index];
            t.pass++;
        }
        t.end++;
    }

    public boolean search(String word) {
        char[] chs = word.toCharArray();
        TrieNode t = this.root;
        int index = 0;
        for (int i = 0; i < chs.length; i++) {
            index = chs[i] - 'a';
            if (t.nexts[index] == null) {
                return false;
            }
            t = t.nexts[index];
        }
        return t.end != 0;
    }

    public boolean startsWith(String prefix) {
        char[] chs = prefix.toCharArray();
        TrieNode t = this.root;
        int index = 0;
        for (int i = 0; i < chs.length; i++) {
            index = chs[i] - 'a';
            if (t.nexts[index] == null) {
                return false;
            }
            else {
                t = t.nexts[index];
            }
        }
        return t.pass != 0;
    }
}

LQyt2012 commented 2 years ago

思路

字符串Trie使用26维数组实现索引。

代码

class Trie:

    def __init__(self):
        self.trie = collections.defaultdict()

    def insert(self, word: str) -> None:
        current = self.trie
        for w in word:
            if w not in current:
                current[w] = collections.defaultdict()
            current = current[w]
        current["#"] = "#"

    def search(self, word: str) -> bool:
        current = self.trie
        for w in word:
            if w not in current:
                return False
            current = current[w]
        return "#" in current

    def startsWith(self, prefix: str) -> bool:
        current = self.trie
        for w in prefix:
            if w not in current:
                return False
            current = current[w]
        return True

type Trie struct {
    isEnd bool
    Next [26]*Trie
}

func Constructor() Trie {
    return Trie{}
}

func (this *Trie) Insert(word string)  {
    current := this
    for i := range word {
        if current.Next[word[i]-'a'] == nil {
            current.Next[word[i]-'a'] = &Trie{}
        }
        current = current.Next[word[i]-'a']
    }
    current.isEnd = true
}

func (this *Trie) Search(word string) bool {
    current := this
    for i := range word {
        if current.Next[word[i]-'a'] == nil {
            return false
        }
        current = current.Next[word[i]-'a']
    }
    return current.isEnd
}

func (this *Trie) StartsWith(prefix string) bool {
    current := this
    for i := range prefix {
        if current.Next[prefix[i]-'a'] == nil {
            return false
        }
        current = current.Next[prefix[i]-'a']
    }
    return true
}

复杂度分析

时间复杂分析：O(N)
空间复杂度：O(N)

JiangWenqi commented 2 years ago

CPP

class Trie {
private:
  bool isWord;
  Trie *children[26];

public:
  Trie() {
    isWord = false;
    for (int i = 0; i < 26; i++)
      children[i] = NULL;
  }

  void insert(string word) {
    Trie *curr = this;
    for (int i = 0; i < word.size(); i++) {
      int idx = word[i] - 'a';
      if (!curr->children[idx])
        curr->children[idx] = new Trie();

      curr = curr->children[idx];
    }
    curr->isWord = true;
  }

  bool search(string word) {
    Trie *curr = this;
    for (int i = 0; i < word.size(); i++) {
      int idx = word[i] - 'a';
      curr = curr->children[idx];
      if (!curr)
        return false;
    }
    return curr->isWord;
  }
  bool startsWith(string prefix) {
    Trie *curr = this;
    for (int i = 0; i < prefix.size(); i++) {

      int idx = prefix[i] - 'a';
      curr = curr->children[idx];
      if (!curr)
        return false;
    }
    return true;
  }
};

tensorstart commented 2 years ago

function Node(val, isEnd){
    this.val = val
    this.child = {}
    this.isEnd = isEnd|| false
}

var Trie = function() {
    this.root = new Node()
};

Trie.prototype.insert = function(word) {
    let cur = this.root
    for (let c of word){
        if (cur.child[c] == null) cur.child[c] = new Node(c)
        cur = cur.child[c]
    }
    cur.isEnd = true;
};

Trie.prototype.search = function(word) {
    let cur = this.root
    for (let c of word){
        if (cur.child[c] == null) return false
        cur = cur.child[c]
    }
    return cur.isEnd
};

Trie.prototype.startsWith = function(prefix) {
    let cur = this.root
    for (let c of prefix){
        if (cur.child[c] == null) return false
        cur = cur.child[c]
    }
    return true
};

ShawYuan97 commented 2 years ago


class TrieNode:
    def __init__(self):
        self.isEnd = False
        self.children = {}

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                node = TrieNode()
                cur.children[ch] = node
            cur = cur.children[ch]
        cur.isEnd = True

    def search(self, word: str) -> bool:
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        if cur.isEnd == True:
            return True
        return False

    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for ch in prefix:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return True 

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Ellie-Wu05 commented 2 years ago

class TrieNode { boolean isEnd; TrieNode[] children;

public TrieNode() { isEnd = true; children = new TrieNode[26]; } }

public class Trie { private TrieNode root;

public Trie() { root = new TrieNode(); }

public void insert(String word) { TrieNode current = root; for(int i=0, L=word.length(); i<L; i++) { int id = word.charAt(i) - 'a'; if(current.children[id]==null) { current.children[id] = new TrieNode(); current.children[id].isEnd = false; } current = current.children[id]; } current.isEnd = true; }

public boolean search(String word) { return search(word, 1); } public boolean startsWith(String prefix) { return search(prefix, 2); } private boolean search(String str, int type) { TrieNode current = root; int i=-1, L=str.length(); while(++i<L) { int id = str.charAt(i) - 'a'; if((current=current.children[id]) == null) return false; } return type==1 ? current.isEnd : true; } }

taojin1992 commented 2 years ago

class Trie {

    TrieNode root = new TrieNode();
    char endSymbol = '*';

    class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        String word;
    }

    public Trie() {

    }

    // O(word.lenght()) time
    public void insert(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            if (!cur.children.containsKey(word.charAt(i))) {
                cur.children.put(word.charAt(i), new TrieNode());
            }
            cur = cur.children.get(word.charAt(i));
        }
        cur.word = word;
        cur.children.put(endSymbol, null);        
    }

    public boolean search(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            if (!cur.children.containsKey(word.charAt(i))) {
                return false;
            }
            cur = cur.children.get(word.charAt(i));
        }
        if (cur.children.containsKey(endSymbol)) return true;
        return false;
    }

    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            if (!cur.children.containsKey(prefix.charAt(i))) {
                return false;
            }
            cur = cur.children.get(prefix.charAt(i));
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

EldinZhou commented 2 years ago


type Trie struct {
    children [26]*Trie
    isEnd    bool
}

func Constructor() Trie {
    return Trie{}
}

func (t *Trie) Insert(word string) {
    node := t
    for _, ch := range word {
        ch -= 'a'
        if node.children[ch] == nil {
            node.children[ch] = &Trie{}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

func (t *Trie) SearchPrefix(prefix string) *Trie {
    node := t
    for _, ch := range prefix {
        ch -= 'a'
        if node.children[ch] == nil {
            return nil
        }
        node = node.children[ch]
    }
    return node
}

func (t *Trie) Search(word string) bool {
    node := t.SearchPrefix(word)
    return node != nil && node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.SearchPrefix(prefix) != nil
}

freedom0123 commented 2 years ago

class Trie {

    Node root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new Node();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        Node p = root;
        for(int i = 0;i < word.length();i ++)
        {
            int u = word.charAt(i) - 'a';
            //如果p这个节点不存在这个儿子，则把它创建出来(有路就直接走，没有路搭个桥都要走过去)
            if(p.son[u] == null) p.son[u] = new Node();
            p = p.son[u]; 
        }
        p.is_end = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Node p = root;
        for(int i = 0;i < word.length();i ++)
        {
            int u = word.charAt(i) - 'a';
            if(p.son[u] == null) return false;
            p = p.son[u]; 
        }
        return p.is_end;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Node p = root;
        for(int i = 0;i < prefix.length();i ++)
        {
            int u = prefix.charAt(i) - 'a';
            if(p.son[u] == null) return false;
            p = p.son[u]; 
        }
        return true;
    }
}
class Node 
{
    boolean is_end;
    Node[] son = new Node[26];
    Node()
    {
        is_end = false;
        for(int i = 0;i < 26;i ++)
            son[i] = null;
    } 
}
/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

revisegoal commented 2 years ago

前缀树

class Trie {
int count;
int preCount;
Trie[] children;

    public Trie() {
        count = 0;
        preCount = 0;
        children = new Trie[26];
    }

    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            if (node.children[word.charAt(i) - 'a'] == null) {
                node.children[word.charAt(i) - 'a'] = new Trie();
            }
            node = node.children[word.charAt(i) - 'a'];
            node.preCount++;
        }
        node.count++;
    }

    public boolean search(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            if (node.children[word.charAt(i) - 'a'] == null) {
                return false;
            }
             node = node.children[word.charAt(i) - 'a'];
        }
        return node.count > 0;
    }

    public boolean startsWith(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            if (node.children[prefix.charAt(i) - 'a'] == null) {
                return false;
            }
            node = node.children[prefix.charAt(i) - 'a'];
        }
        return node.preCount > 0;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

time: 创建O(1)，其他操作O(n)
space: O(C * n)

KWDFW commented 2 years ago

Day73

208、实现Trie

javascript #前缀树

思路

1、构造前缀树

代码

var Trie = function() {
  this.children = {};
};

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
  let node = this.children;
  for (const ch of word) {
    if (!node[ch]) {
      node[ch] = {};
    }
    node = node[ch];
  }
  node.isEnd = true;
};

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
  let node = this.children;
  for (const ch of word) {
    if (!node[ch]) {
      return false;
    }
    node = node[ch];
  }
  return node.isEnd === true;
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
  let node = this.children;
  for (const ch of prefix) {
    if (!node[ch]) {
      return false;
    }
    node = node[ch];
  }
  return true;
};

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

复杂度分析

时间复杂度：O(n)

空间复杂度：O(s)

asuka1h commented 2 years ago


class TrieNode{
    public:
    TrieNode *next[26];
    bool isString;
    TrieNode(): next{}, isString{false}{
    }
};

class Trie {
private:
TrieNode*root;
public:

    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode*p = root;
        for(int i = 0; i < word.size();++i){
            if(p->next[word[i]-'a']==NULL){
                p->next[word[i]-'a'] = new TrieNode();
            }
            p = p->next[word[i]-'a'];
        }
        p->isString = true;
    }

    bool search(string word) {
        TrieNode *p = root;
        for(int i = 0; i < word.size();++i){
            if(p == NULL){
                return false;
            }
            p = p->next[word[i]-'a'];
        }
        if(p == NULL || p->isString == false){
            return false;
        }
        return true;
    }

    bool startsWith(string prefix) {
        TrieNode *p = root;
        for(int i = 0; i < prefix.size(); ++i){
            p = p->next[prefix[i]-'a'];
            if(p== NULL) {
                return false;
            }

        }
         return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

TonyLee017 commented 2 years ago

思路

字典树

代码

class Trie:
def __init__(self):
    self.children = [None] * 26
    self.isEnd = False

def searchPrefix(self, prefix: str) -> "Trie":
    node = self
    for ch in prefix:
        ch = ord(ch) - ord("a")
        if not node.children[ch]:
            return None
        node = node.children[ch]
    return node

def insert(self, word: str) -> None:
    node = self
    for ch in word:
        ch = ord(ch) - ord("a")
        if not node.children[ch]:
            node.children[ch] = Trie()
        node = node.children[ch]
    node.isEnd = True

def search(self, word: str) -> bool:
    node = self.searchPrefix(word)
    return node is not None and node.isEnd

def startsWith(self, prefix: str) -> bool:
    return self.searchPrefix(prefix) is not None

复杂度分析

时间复杂度：O(n)
空间复杂度：O(s)

flyzenr commented 2 years ago

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.lookup = {}

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        tree = self.lookup
        for a in word:
            if a not in tree:
                tree[a] = {}
            tree = tree[a]
        # 单词结束标志
        tree["#"] = "#"

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        tree = self.lookup
        for a in word:
            if a not in tree:
                return False
            tree = tree[a]
        if "#" in tree:
            return True
        return False

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        tree = self.lookup
        for a in prefix:
            if a not in tree:
                return False
            tree = tree[a]
        return True

maggiexie00 commented 2 years ago

def __init__(self):
    self.children = [None] * 26
    self.isEnd = False

def searchPrefix(self, prefix: str) -> "Trie":
    node = self
    for ch in prefix:
        ch = ord(ch) - ord("a")
        if not node.children[ch]:
            return None
        node = node.children[ch]
    return node

def insert(self, word: str) -> None:
    node = self
    for ch in word:
        ch = ord(ch) - ord("a")
        if not node.children[ch]:
            node.children[ch] = Trie()
        node = node.children[ch]
    node.isEnd = True

def search(self, word: str) -> bool:
    node = self.searchPrefix(word)
    return node is not None and node.isEnd

def startsWith(self, prefix: str) -> bool:
    return self.searchPrefix(prefix) is not None

xiayuhui231 commented 2 years ago

public void insert(String word) { Trie cur = this; for(int i = 0; i < word.length(); i++) { int c = word.charAt(i) - 'a'; Trie t = cur.root[c]; if(t == null) { t = new Trie(); cur.root[c] = t; } cur = t; } cur.isLeaf = true; }

public boolean search(String word) { Trie cur = this; for(int i = 0; i < word.length(); i++) { int c = word.charAt(i) - 'a'; Trie t = cur.root[c]; if(t == null) return false; cur = t; } return cur.isLeaf; }

public boolean startsWith(String prefix) { Trie cur = this; for(int i = 0; i < prefix.length(); i++) { int c = prefix.charAt(i) - 'a'; Trie t = cur.root[c]; if(t == null) return false; cur = t; } return true; }

asuka1h commented 2 years ago



vector<vector<int>> ret;
class Solution {

public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {

        TrieNode node;
        int n=smalls.size();
        ret.clear();
        ret.resize(n);
        for(int i=0;i<n;i++){
            string s=smalls[i];
            if(s.empty())continue;
            node.insert(s,i);
        }
        for(int i=0;i<big.size();i++){
            node.search(big.substr(i),i);
        }
        return ret;
    }
    struct TrieNode{
        int small_id;
        TrieNode* children[26];
        TrieNode():small_id(-1),children{}{
        }
        void insert(string word,int k){
            TrieNode* root=this;
            for(int i=0;i<word.size();i++){
                int index=word[i]-'a';
                if(root->children[index]==nullptr){
                    root->children[index]=new TrieNode();
                }
                root=root->children[index];
            }
            root->small_id=k;
        }
        void search(string word,int k){
            TrieNode* root=this;
            for(int i=0;i<word.size();i++){
                int index=word[i]-'a';
                if(root->small_id!=-1){
                    ret[root->small_id].push_back(k);
                }
                if(root->children[index]==nullptr){
                    return;
                }
                root=root->children[index];
            }
            if(root->small_id!=-1){
                    ret[root->small_id].push_back(k);
            }
        }
    };

};

leetcode-pp / 91alg-7-daily-check

【Day 73 】2022-06-12 - 实现 Trie (前缀树 #78

实现 Trie (前缀树

入选理由

题目地址

前置知识

题目描述

思路

代码

复杂度

Idea

Code

Idea

code

Day73 思路

复杂度分析

代码

代码

Idea

Code

思路

代码

复杂度分析

前缀树

javascript #前缀树

思路

代码

复杂度分析

思路

代码

复杂度分析