ARTS - Week 7

ARTS - Week 7

ARTS 是耗叔发起的一项活动,每周完成以下内容:

Algorithm - 至少做一个 LeetCode 上的算法题
Review - 阅读并点评至少一篇英文技术文章
Tip - 学习至少一个技术技巧
Share - 至少分享一篇有观点和思考的技术文章

Algorithm

LeetCode Problems 208 - Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Difficulty: Medium

Example:

Implement Trie Example

Solution

字典树

使用 Python 中的嵌套 dict 和 Ruby 中的嵌套 hash 结构,构建字典树

# Python

class Trie:

    def __init__(self):
        self.root = {}
        self.end_of_word = "#"

    def insert(self, word):
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node[self.end_of_word] = self.end_of_word

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return self.end_of_word in node

    def startsWith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True
# Ruby

class Trie
    def initialize()
        @root = {}
        @end_of_node = "#"
    end
    
    def insert(word)
        node = @root
        word.each_char do |char|
            node[char] ||= {}
            node = node[char]
        end
        node[@end_of_node] = @end_of_node
    end
    
    def search(word)
        node = @root
        word.each_char do |char|
            return false if !node.keys.include?(char)
            node = node[char]
        end
        return node.keys.include?(@end_of_node)
    end
    
    def starts_with(prefix)
        node = @root
        prefix.each_char do |char|
            return false if !node.keys.include?(char)
            node = node[char]
        end
        return true
    end
end

运行结果

Python:
Runtime: 180 ms.
Your runtime beats 88.48 % of python3 submissions.

Ruby:
Runtime: 188 ms.
Your runtime beats 37.04 % of ruby submissions.


Review

FIZZBUZZ IN 10 LANGUAGES!

本文作者将 FizzBuzz 这个常见的简单面试题,用10种不同语言来解答。


# ARTS 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×