ARTS #50

Algorithm

本周选择的算法题是：Word Search II

规则如下：

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

Note:

All inputs are consist of lowercase letters a-z.
The values of words are distinct.

Solution

Runtime：272 ms，快过 72.41%。

Memory：28 MB，低于 50%。

class Solution:
    class Trie:
        def __init__(self):
            self.root = {}
        
        def add(self, word: str):
            node = self.root
            for char in word:
                if char not in node:
                    node[char] = {}
                node = node[char]
            node['#'] = word
        
        def startswith(self, char: str, begin: {}) -> {}:
            node = begin if begin else self.root
            if char in node:
                return node[char]
        
        def remove(self, word: str):
            def _remove(node, depth: int):
                if len(word) == depth:
                    if self.is_word(node):
                        del node['#']
                    return
                char = word[depth]
                found = self.startswith(char, node)
                if found:
                    _remove(found, depth+1)
                    if len(found) == 0:
                        del node[char]
                else:
                    return

            _remove(self.root, 0)
        
        def is_empty(self, node) -> bool:
            return len(node) == 0 and not self.is_word(node)

        def is_word(self, node: {}) -> bool:
            return '#' in node if node else False

    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        trie = Solution.Trie()
        for word in words:
            trie.add(word)
        
        ans = []
        for i in range(len(board)):
            for j in range(len(board[0])):
                self.find_word(board, i, j, trie, set(), ans)
        return ans
    
    def find_word(self, board, i, j, trie, visited, ans, node = None):
        char = board[i][j]
        position = trie.startswith(char, node)
        if position:
            visited.add((i, j))
            if trie.is_word(position):
                word = position['#']
                trie.remove(word)
                ans.append(word)
            test_positions = [
                (i - 1, j),
                (i + 1, j),
                (i, j - 1),
                (i, j + 1),
            ]
            for test_position in test_positions:
                if test_position in visited: continue
                if not (0 <= test_position[0] < len(board)): continue
                if not (0 <= test_position[1] < len(board[0])): continue
                self.find_word(board, test_position[0], test_position[1], trie, visited, ans, position)
            visited.remove((i, j))

代码上不够简洁，没有充分利用 python 的语法，优化后：

class Solution:
  def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # 初始化 trie
        WORD_KEY = '$'
        trie = {}
        for word in words:
            node = trie
            for char in word:
                node = node.setdefault(char, {})
            node[WORD_KEY] = word
        
        # 回溯
        ans = []
        def backtracking(i, j, parent):
            char = board[i][j]
            node = parent[char]

            word = node.pop(WORD_KEY, None)
            if word: ans.append(word)
            
            board[i][j] = '#' # 不需要额外的空间记录访问过的 Cell
            for i_offset, j_offset in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                new_i, new_j = i + i_offset, j + j_offset
                if not (0 <= new_i < len(board)): continue
                if not (0 <= new_j < len(board[0])): continue
                if board[new_i][new_j] not in node: continue
                backtracking(new_i, new_j, node)

            if not node: # 空节点
                del parent[char]

            board[i][j] = char
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] in trie:
                    backtracking(i, j, trie)
        return ans

减化了 Trie 的实现
优化了访问过的 Cell 的记录方式
充分利用了 setdefault 和 pop
更简单的 offset 计算

Review

History of Auto Layout constraints

这篇文章回顾了苹果 Auto Layout API 的历史，把 iOS6 到至今为止的改变完整的呈现给了大家，从中能够看出苹果处理问题的方式以及背后的思考。

ps: 考虑用原生 API 代替第三方布局库。

Tip

Automate repetitive tasks with custom Git commands 给 git 添加自定义命令

firefox-ios#UserAgent 的开源项目，这个文件展示了如何通过代码自己构建 UA。

Algorithm

Solution

Review

Tip

Share