Word Search解题报告

怼烎@ 2021-09-18 09:20 211阅读 0赞

### DFS(深度优先搜索) ###

首先介绍下什么是DFS吧。

DFS我的理解其实就是一条路走到黑，发现没路了，再回到上一个地方，看有没有路。

1.  查看根节点是否满足条件
    
    满足条件， 加入栈
    
    不满足，pass，栈为空，退出循环
2.  查看该节点下的直接子节点是否满足条件
    
    满足条件，重复步骤2
    
    不满足条件，将父节点加入栈
3.  不断循环，直到栈为空

大家也看到了，这种概念一理清楚，就知道，可以用递归去实现DFS。

### Word Search ###

[Word Search][]

首先思路应该很明显了，我们先找到board中跟word的首字母相同的坐标，然后把这个设置为当前的位置进行深度优先搜索，也就是查找当前位置的上下左右的字母，看看是否符合条件，不符合条件的话，就返回。符合的话，就把该位置设置为当前位置，重复上面的步骤，直到找到整个word为止。

但是有几个点需要主要:

1.  查找的位置，不能超过board的边界
2.  已经查找过的位置，需要标记出来，避免重复查找。这里我引入了一个visited数组，作为标记。

代码如下:

class Solution {
        func exist(_ board: [[Character]], _ word: String) -> Bool {
            guard board.count > 0 else { return false }
    
            var visited = Array(repeating: Array(repeating: false, count: board[0].count), count: board.count)
            let cs = Array(word)
            for i in 0..<board.count {
              for j in 0..<board[0].count {
                if cs[0] == board[i][j] && dfs(board, i, j, cs, 0, &visited) {
                  return true
                }
              }
            }
            return false
          }
    
          func dfs(_ board: [[Character]], _ i: Int, _ j: Int, _ cs: [Character], _ pos: Int, _ visited: inout [[Bool]]) -> Bool {
            guard cs.count > pos else { return true }
    
            if (i < 0 || i >= board.count || j < 0 || j >= board[0].count || board[i][j] != cs[pos] || visited[i][j]) {
              return false
            }
            visited[i][j] = true
            if dfs(board, i - 1, j, cs, pos + 1, &visited) ||
              dfs(board, i + 1, j, cs, pos + 1, &visited) ||
              dfs(board, i, j - 1, cs, pos + 1, &visited) ||
              dfs(board, i, j + 1, cs, pos + 1, &visited) {
              return true
            }
            visited[i][j] = false
            return false
          }
    }
    复制代码

### Word Search 2 ###

[212. Word Search II][]

看了题目后，首先的想法就是，把这个words遍历一遍，根据上面的dfs将符合的word给过滤出来。当然理想很丰满，首先就是，会出现重复的word，这个没有过。然后把重复的给去除了:

Array(Set(results))
    复制代码

提交后，毫无意外的，超时了。

其实你算下复杂度，如果按照上面的方法的话，复杂度应该就是:

O(k * m * n * l * x)
    
    k: words数组的数量
    m: board的长
    n: board的宽
    l: word的最长的长度
    x: 首字母跟board中字符相同的数量
    复制代码

给你们感受下，没有过的测试数据:

这种情况下，该算法的执行时间就会变的非常的长，当然这还不是最差的情况，最差的情况是，board中的所有字符都是'a'。

所以下面我们引入了字典树:

#### 字典树 ####

如图所示，字典树就是将所有的word的字符，变成树中的一个个节点，然后我们遍历完一颗树后，就能找到完整的word。

有了这个思路之后，我们把上面的dfs少加改造:

func dfs(_ board: [[Character]], _ i: Int, _ j: Int, _ trie: TrieNode, _ str: String, _ visited: inout [[Bool]], _ res: inout [String]) {
        guard i >= 0 && i < board.count && j >= 0 && j < board[0].count && !visited[i][j] else { return }
        
        let c = board[i][j]
        guard let node = trie.child[c] else { return }
        
        let str = str + String(board[i][j])
        if node.isEnd && !res.contains(str) {
          res.append(str)
        }
        
        visited[i][j] = true
        dfs(board, i - 1, j, node, str, &visited, &res)
        dfs(board, i + 1, j, node, str, &visited, &res)
        dfs(board, i, j - 1, node, str, &visited, &res)
        dfs(board, i, j + 1, node, str, &visited, &res)
        visited[i][j] = false
      }
    复制代码

我们把当前遍历到的node与board中的字符做一个对比，如果存在该字符的话，我们就认为是符合条件的，否者的话，直接返回结果。重复上述步骤，直到找到叶子节点。

构造字典树:

class TrieNode {
        var isEnd: Bool
        var child: [Character: TrieNode]
        
        init() {
          self.isEnd = false
          self.child = [:]
        }
      }
    
    func buildTrie(_ words: [String]) -> TrieNode {
        let root = TrieNode()
        for word in words {
         insert(root, word)
        }
        return root
      }
      
      func insert(_ root: TrieNode, _ word: String) {
        var node = root
        for c in word {
          if node.child[c] == nil {
            node.child[c] = TrieNode()
          }
          node = node.child[c]!
        }
        node.isEnd = true
      }
    复制代码

好了，谢谢大家。

[Word Search]: https://link.juejin.im?target=https%3A%2F%2Fleetcode.com%2Fproblems%2Fword-search%2F
[212. Word Search II]: https://link.juejin.im?target=https%3A%2F%2Fleetcode.com%2Fproblems%2Fword-search-ii%2F