[LeetCode] Implement Trie

[LeetCode] Implement Trie

---

 

-문제 링크

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

Implement Trie (Prefix Tree) - LeetCode

 

 

---

- 설명

직접 Trie(트라이)를 짜보는 문제이다.

원리를 안다면 금방 짤 수 있고 소스코드도 많다.

스터디원마다 flag를 짜는 법이 제각각이라서 신기했다. 

 

---

- Code

class Trie:
    
    
    def __init__(self):
        
        self.head ={}

    def insert(self, word: str) -> None:
        
        curNode = self.head
        
        for alphabet in word:
            if(alphabet not in curNode):
                curNode[alphabet] = {} #create new alphabet children
            curNode = curNode[alphabet]
            
        curNode["flag"] = word
            
            
    def search(self, word: str) -> bool:
        
        curNode = self.head
        
        for alphabet in word:
            if(alphabet not in curNode):
                return False
            else:
                curNode = curNode[alphabet]
                
        if("flag" in curNode):
            return True
        else:
            False

    def startsWith(self, prefix: str) -> bool:
        
        curNode = self.head
        
        for alphabet in prefix:
            if(alphabet not in curNode):
                return False
            else:
                 curNode = curNode[alphabet]
        return True

 

---

-Time