土豆炒青椒

小白坚持刷 212 ~ 搜单词 2

日刷 leetcode 三百题,此生无悔做码工。横批:永无止境地刷

基本信息

  • 题号:212
  • 题厂:脸书
  • 难度系数:高



#79 升级版。

还是在 m * n 的矩阵中找单词。较 #79 不同的是,本次要搜寻一系列单词,如果单词出现在了矩阵中,则将出现单词以数组形式返回。

欲解 212,需先理解 79.

解题思路

  • 按照 #79 的思路,可以先将目标单词根据单词首字母整理成 hashmap。再遍历矩阵,当格子和 hashmap 的 key 匹配时,再进行和 #79 类似的 上、下、左、右 四个方向查找。如果找到,则将单词添加进返回数组……
# 在 79 原理之上,引入 hashmap 的升级解法如下:  
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # 「首字母」:「首字母对应单词数组。。。」
        wordList = {}
        
        for word in words:
            if word[0] not in wordList:
                wordList[word[0]] = [word]
            else:
                wordList[word[0]].append(word)
                
        row, col = len(board), len(board[0])
        res = []
        
        def findWord(word, r, c, i, path):
            if i == len(word):
                return True
            
            if (r < 0 
               or r >= row
               or c < 0
               or c >= col
               or (r, c) in path
               or board[r][c] != word[i]):
                return False
            
            path.add((r, c))
            res = (findWord(word, r + 1, c, i + 1, path)
                  or findWord(word, r - 1, c, i + 1, path)
                  or findWord(word, r, c + 1, i + 1, path)
                  or findWord(word, r, c - 1, i + 1, path))
            path.remove((r, c))
            
            return res
            
        for r in range(row):
            for c in range(col):
                if board[r][c] in wordList:
                    for word in wordList[board[r][c]]:
                        if findWord(word, r, c, 0, set()) and word not in res:
                            res.append(word)
                            
        return res


  • 以上解法在逻辑上并无漏洞,但算法太费时,代码无法通过测试,所以需要引入更高级的数据结构——trie,简化时间复杂度
维基百科。。。
  • 简单理解,相对线性数据结构 hashmap,trie 类似一个树状字典。在遍历单词时,如果当前字符存在,就往下继续遍历;如果没有就提前返回 false。每个单词的末尾,即 leaf node,需要标注为 endWord。
  • 引入 trie 以后,原本遍历 hashmap 时需要的 O(n)的费时可以简化为 O(1)。
  • 为了进一步简化时间复杂度,在 trie 中添加 removeWord 方法:如果单词被找到,就删除它,因为本题中目标单词序列没有重复。。。



# 引入 Trie 后的完整代码如下 🥲
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False
        self.refs = 0

    def addWord(self, word):
        cur = self
        cur.refs += 1
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
            cur.refs += 1
        cur.isWord = True

    def removeWord(self, word):
        cur = self
        cur.refs -= 1
        for c in word:
            if c in cur.children:
                cur = cur.children[c]
                cur.refs -= 1

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()
        for w in words:
            root.addWord(w)

        ROWS, COLS = len(board), len(board[0])
        res, visit = set(), set()

        def dfs(r, c, node, word):
            if (
                r < 0
                or c < 0
                or r == ROWS
                or c == COLS
                or board[r][c] not in node.children
                or node.children[board[r][c]].refs < 1
                or (r, c) in visit
            ):
                return

            visit.add((r, c))
            node = node.children[board[r][c]]
            word += board[r][c]
            if node.isWord:
                node.isWord = False
                res.add(word)
                root.removeWord(word)

            dfs(r + 1, c, node, word)
            dfs(r - 1, c, node, word)
            dfs(r, c + 1, node, word)
            dfs(r, c - 1, node, word)
            visit.remove((r, c))

        for r in range(ROWS):
            for c in range(COLS):
                dfs(r, c, root, "")

        return list(res)



Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i][j] is a lowercase English letter.
  • 1 <= words.length <= 3 * 104
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • All the strings of words are unique.

对比 79, 升级后的 212 要求算法能够搜索高达 3 * 104 单词序列……考试时,听到这种大数字,基本上预示明眼可见的一些简单解法,肯定是通不过的了……难题登场了……🥲


Big O

  • Time:引入 trie 后,复杂度从 O(n * m * 4 * k * 单词长度 )可以简化为 O(n * m * 4 * 单词长度 )
  • space:O(k),k 为目标搜寻单词序列长度。如果要搜 1000 个单词,返回 res 长度最坏的时候有 1000 😭

本题十分复杂,如有错误,欢迎大佬评论区指证。


测试

  • 序列中一些单词存在,一些单词不存在
  • 当然不要忘了重点:一次搜 3000 个单词的极限值……



总结

  • 不少难题是由中档、简单档题 循序渐进 + 升级 + 变形 + 组装 而来,例如本题在 79 的 backtracking 等基础之上又组装添加了 trie 元素。欲解难题,需要对基础题有深度理解
  • 一些难题并不是拿到题目后完全没有思路,例如本题……而是那些显而易见的简易思路(例如 brute force)将造成时间复杂度超级复杂,需要引入高档数据结构(如本题涉及的 trie 知识点)又或者高档算法思路(如 dynamic programming🙈)优化……即难题难点所在……😭
  • 考试时如果遇上这种题,如果反应不过来先把 brute force + hashmap 的普通解法拿出来给考官讨论下,总比一行代码不写得 0 分强。如果考官暗示 trie,一定要接住……😭

Like my work??
Don't forget to support or like, so I know you are with me..

CC BY-NC-ND 2.0

小白继续刷 79 ~ 搜单词

Want to read more ?

Login with one click and join the most diverse creator community.