ARTS #116

Algorithm

规则

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints:

1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters.
At most 3 * 104 calls in total will be made to insert, search, and startsWith.

Solution

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = {}
        self.word_key = '$'

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.trie
        for char in word:
            node = node.setdefault(char, {})
        node[self.word_key] = word

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.trie
        for char in word:
            if char not in node: return False
            node = node[char]
        return self.word_key in node

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

# 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)

Review

5 Reasons Why Rust Is The Future

作者列出的5个原因如下：

提高了内存安全性
社区在高速发展
执行效率高
能被广泛应用
背后有商业公司

这些优势名副其实，不过 Rust 也有一个很大的劣势（可能会影响其大规模应用）：学习曲线巨高。就算是有经验的工程师也要经过至少3-6个月的时间才能写出高效的 Rust 代码，而 Go 只需要2周左右，Python 更短。

但 Rust 是一门很全面的语言，一旦“上手”，无论是系统编程，亦或是 Web 开发，Rust 都能很好的 cover 住。

Tip

正式在 DevOps 中引入静态分析流程，过程还算顺利，iOS 有个小坑：UseModernBuildSystem 为 YES 时似乎不支持 CLANG_ANALYZER_OUTPUT_DIR。

一张多语言方案的草图：

该方案要解决的关键问题是：

在研发人员、代码平台、翻译平台三者之间解耦
有 UI 验收环节检查不同翻译物料对页面的影响
有兜底策略，保障线上环境的物料完备性
能自动导入、导出语言包

由于落地周期偏长，多语言项目在稿定内部是分阶段落地的。

Algorithm

规则

Solution

Review

Tip

Share