最近看到YELP的电面有问到字符串的一道题, 搜了一下 发现了 TRIE 字典树, 学一下~

Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.

Trie树又被称为字典树、前缀树，是一种用于快速检索的多叉树。Tried树可以利用字符串的公共前缀来节省存储空间。
但如果系统存在大量没有公共前缀的字符串，相应的Trie树将非常消耗内存。（下图为Wiki上的Trie树示意图， Wiki）


Trie树的基本性质如下：
• 根节点不包括字符，除根节点外每个节点包括一个支付。
• 从根节点到某一节点，路径上经过的字符连接起来，即为对应的字符串。
• 每个节点的所有子节点包含的字符串各不相同。
本题中的Trie树可以简单实现如下：
Trie树节点数据结构定义如下：

1.    val表示该节点对应的字符
2.    子节点简单用一个数组表示，这样实现比较简单，但比较耗费内存
3.    isWord标记从根节点到该节点是否表示一个单词，还是另一单词的前缀。

    1.    class TrieNode {  
    2.    public:  
    3.        char var;  
    4.        bool isWord;  
    5.        TrieNode* children[26];  
    6.        // Initialize your data structure here.  
    7.        TrieNode() {  
    8.            var = 0;  
    9.            isWord = false;  
    10.            memset(children, 0x0, sizeof(TreeNode*)*26);  
    11.      
    12.        }  
    13.        TrieNode(char c){  
    14.            var = c;  
    15.            isWord = false;  
    16.            memset(children, 0x0, sizeof(TreeNode*)*26);  
    17.        }  
    18.    };

Trie树的实现算法如下：

    1.    class Trie {  
    2.    public:  
    3.        Trie() {  
    4.            root = new TrieNode();  
    5.        }  
    6.      
    7.        // Inserts a word into the trie.  
    8.        void insert(string word) {  
    9.            TrieNode* pNode = root;  
    10.            if (word.length() <= 0)  
    11.            {  
    12.                return;  
    13.            }  
    14.            for (int i= 0; i<word.length(); i++)  
    15.            {  
    16.                char c= word[i];  
    17.                if (pNode->children[c-'a'] == 0)  
    18.                {  
    19.                    TrieNode *pNew = new TrieNode(c);  
    20.                    pNode->children[c-'a'] = pNew;  
    21.                }  
    22.                pNode = pNode->children[c-'a'];  
    23.            }  
    24.            pNode->isWord = true;  
    25.        }  
    26.      
    27.        // Returns if the word is in the trie.  
    28.        bool search(string word) {  
    29.            TrieNode *pNode = root;  
    30.            if (word.length() <= 0)  
    31.                return true;  
    32.            for (int i =0; i<word.length(); i++)  
    33.            {  
    34.                char c = word[i];  
    35.                pNode = pNode->children[c-'a'];  
    36.                if (pNode == NULL)  
    37.                    return false;  
    38.            }  
    39.            return pNode->isWord;  
    40.        }  
    41.      
    42.        // Returns if there is any word in the trie  
    43.        // that starts with the given prefix.  
    44.        bool startsWith(string prefix) {  
    45.            TrieNode *pNode = root;  
    46.            if (prefix.length()<=0)  
    47.                return true;  
    48.            for (int i=0; i<prefix.length(); i++)  
    49.            {  
    50.                char c = prefix[i];  
    51.                pNode = pNode->children[c-'a'];  
    52.                if (pNode == NULL)  
    53.                    return false;  
    54.            }  
    55.            return true;  
    56.        }  
    57.        void freeTrieNode(TrieNode* pNode){  
    58.            if (pNode == NULL)  
    59.                return;  
    60.            for (int i=0; i<26;i++)  
    61.            {  
    62.                TrieNode* pChild = pNode->children[i];  
    63.                if (pChild != NULL)  
    64.                {  
    65.                    freeTrieNode(pChild);  
    66.                }  
    67.            }  
    68.            free(pNode);  
    69.        }  
    70.        ~Trie(){  
    71.            freeTrieNode(root);  
    72.        }  
    73.    private:  
    74.        TrieNode* root;  
    75.    };

下面是PYTHON的一个实现

准备就常用的数据结构写一个REP吧/

class TrieTree(object):

  def __init__(self):
    self.tree = {}

  def add(self, word):
    tree = self.tree

    for char in word:
      if char in tree:
        tree = tree[char]
      else:
        tree[char] = {}
        tree = tree[char]

    tree['exist'] = True

  def search(self, word):
    tree = self.tree

    for char in word:
      if char in tree:
        tree = tree[char]
      else:
        return False

    if "exist" in tree and tree["exist"] == True:
      return True
    else:
      return False

tree = TrieTree()
tree.add("abc")
tree.add("bcd")
print(tree.tree)
# Print {'a': {'b': {'c': {'exist': True}}}, 'b': {'c': {'d': {'exist': True}}}}
print(tree.search("ab"))
# Print False
print(tree.search("abc"))
# Print True
print(tree.search("abcd"))
# Print False

trivial example

leetcode第一题, two sum,

这个了有点时间… 我在复制数组的时候直接用的a = b, 但是在PYTHON里面这样拷贝会把地址也传递过去, 当del a[2]的时候也会改变b的值, 开始没有注意, 所以老是出错, 这题还是比较简单的一道题 = =

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in nums:
            dif = target - i
            nums1 = nums[:]
            a = nums1.index(i)
            del nums1[a]
            if dif in nums1 :
                b = nums1.index(dif) + 1
                return [a,b]

话说还是第一次在leetcode上面做题, 以后没事多来刷一下吧~~ 以后面试也好弄..

开一个rep来记录一下