[Swift]LeetCode212.单词搜索II|WordSearchII

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10197862.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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: 
words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Output: ["eat","oath"]

Note:
You may assume that all inputs are consist of lowercase letters a-z.

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

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

输出: ["eat","oath"]

说明:
你可以假设所有输入都由小写字母 a-z 组成。

提示:

你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？
如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题：实现Trie（前缀树）。

328ms

  1 class TrieNode: CustomStringConvertible {
  2     var description: String {
  3         return "word:\(word)   children:\(children)"
  4     }
  5 
  6     var word: String? = nil
  7     var children = [Character:TrieNode]()
  8 }
  9 
 10 class TrieTree {
 11     let root = TrieNode()
 12 
 13     func insert(_ word:String) {
 14         var node: TrieNode? = root
 15         for c in word{
 16             guard let _node = node else {
 17                 continue
 18             }
 19             if let child = _node.children[c] {
 20                 node = child
 21             } else {
 22                 node = TrieNode()
 23                 _node.children[c] = node
 24             }
 25         }
 26         node?.word = word
 27 
 28         // print(root)
 29     }
 30 
 31     func hasPrefix(_ prefix:[Character]) -> Bool {
 32         var node: TrieNode? = root
 33         for c in prefix{
 34             guard let _node = node else {
 35                 return false
 36             }
 37             if let child = _node.children[c] {
 38                 node = child
 39             } else {
 40                 return false
 41             }
 42         }
 43         return true
 44     }
 45 
 46     func hasWord(_ word:[Character]) -> Bool {
 47         var node: TrieNode? = root
 48         for c in word{
 49             guard let _node = node else {
 50                 return false
 51             }
 52             if let child = _node.children[c] {
 53                 node = child
 54             } else {
 55                 return false
 56             }
 57         }
 58         return node?.word == nil ? false : true
 59     }
 60 }
 61 
 62 
 63 class Solution {
 64     func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
 65         
 66         
 67         let trie = TrieTree()
 68         var record = [[Bool]](repeating:[Bool](repeating:false, count:board[0].count), count:board.count)
 69         var result = Set<String>()
 70         
 71         
 72         for word in words {
 73             trie.insert(word)
 74         }
 75         
 76         for x in 0..<board.count {
 77             for y in 0..<board[0].count {
 78                 guard let node = child(board,trie.root,x,y) else {
 79                     continue
 80                 }
 81                 search(board,&record,node,x,y, &result)
 82             }
 83         }
 84 
 85         return Array(result)
 86 
 87     }
 88     
 89     func child(_ board: [[Character]],_ node:TrieNode,_ x:Int,_ y:Int) -> TrieNode? {
 90         guard x < board.count, x >= 0, y < board[0].count, y >= 0 else {
 91             return nil
 92         }
 93         
 94         return node.children[board[x][y]]
 95     }
 96     
 97     func search (_ board: [[Character]],_ record:inout [[Bool]], _ node:TrieNode,_ x:Int, _ y:Int, _ result:inout Set<String>) {
 98         guard x < board.count, x >= 0, y < board[0].count, y >= 0, !record[x][y] else {
 99             return
100         }
101         
102         // print("\(x):\(y)    \(board[x][y])")
103         
104         if let word = node.word {
105             result.insert(word)
106         }
107         
108         record[x][y] = true
109         
110         if let nextNode = child(board,node,x+1,y) {
111             search(board,&record,nextNode,x+1,y, &result)
112         }
113         
114         if let nextNode = child(board,node,x-1,y) {
115             search(board,&record,nextNode,x-1,y, &result)
116         }
117         
118         if let nextNode = child(board,node,x,y+1) {
119             search(board,&record,nextNode,x,y+1, &result)
120         }
121         
122         if let nextNode = child(board,node,x,y-1) {
123             search(board,&record,nextNode,x,y-1, &result)
124         }
125         
126         record[x][y] = false
127     }
128 }

348ms

 1 class Solution {
 2     
 3     let lowerLetterUnicodeStart = Character("a").char2Int()
 4     
 5     func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
 6         var board = board
 7         var result = [String]()
 8         let root = buildTrie(words)
 9         let (m, n) = (board.count, board[0].count)
10         
11         func dfs(_ i: Int, _ j: Int, _ root: TrieNode) {
12             if i < 0 || j < 0 || i >= m || j >= n { return }
13             let char = board[i][j]
14             let charIndex = char.char2Int() - lowerLetterUnicodeStart
15             if char == "#" || root.next[charIndex] == nil { return }
16             let root = root.next[charIndex]!
17             if let rootWord = root.word {
18                 result.append(rootWord)
19                 root.word = nil
20             }
21             board[i][j] = "#"
22             dfs(i - 1, j, root)
23             dfs(i, j - 1, root)
24             dfs(i + 1, j, root)
25             dfs(i, j + 1, root)
26             board[i][j] = char
27         }
28         
29         for i in 0..<m {
30             for j in 0..<n {
31                 dfs(i, j, root)
32             }
33         }
34         return result
35     }
36     
37     func buildTrie(_ words: [String]) -> TrieNode {
38         let root = TrieNode()
39         for word in words {
40             var point = root
41             for char in word {
42                 let charIndex = char.char2Int() - lowerLetterUnicodeStart
43                 if point.next[charIndex] == nil { point.next[charIndex] = TrieNode() }
44                 point = point.next[charIndex]!
45             }
46             point.word = word
47         }
48         return root
49     }
50 }
51 
52 class TrieNode {
53     var next: [TrieNode?] = Array(repeating: nil, count: 26)
54     var word: String?
55 }
56 
57 extension Character {
58     func char2Int() -> Int {
59         return Int(self.unicodeScalars.first!.value)
60     }
61 }

364ms

 1 class Solution {
 2     func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
 3         var board = board
 4         var trie = Trie()
 5         
 6         for word in words {
 7             trie.insert(word)
 8         }
 9         
10         var result = [String]()
11         
12         if board.isEmpty {
13             return result
14         }
15         
16         for i in 0 ..< board.count {
17             for j in 0 ..< board[0].count {
18                 dfs(&board, i, j, trie.root, &result)
19             }
20         }
21         return result
22     }
23     
24     func dfs(_ board: inout [[Character]], _ i: Int, _ j: Int, _ trie: TrieNode, _ result: inout [String]) {
25         var trie = trie
26         
27         if board[i][j] == "*" || trie.children[board[i][j]] == nil {
28             return
29         }
30         
31         trie = trie.children[board[i][j]]!
32         
33         if trie.word != "*" {
34             result.append(trie.word)
35             trie.word = "*"
36         }
37         
38         var cur = board[i][j]
39         board[i][j] = "*"
40         if (i < board.count-1) { dfs(&board, i+1, j, trie, &result) }
41         if (i > 0) { dfs(&board, i-1, j, trie, &result) }
42         if (j < board[0].count-1) { dfs(&board, i, j+1, trie, &result) }
43         if (j > 0) { dfs(&board, i, j-1, trie, &result) }
44         board[i][j] = cur
45         return
46     }
47 }
48 
49 class Trie {
50     public var root = TrieNode()
51     
52     public func insert(_ word: String) {
53         var head = root
54         
55         for w in word {
56             if head.children[w] == nil {
57                 head.children[w] = TrieNode()
58             }
59             
60             head = head.children[w]!
61         }
62         head.word = word
63     }
64 }
65 
66 class TrieNode {
67     public var word: String = "*"
68     public var children = [Character : TrieNode]()
69 }

384ms

 1 class TrieNode {
 2     var word: String? = nil
 3     var children = [Character:TrieNode]()
 4 }
 5 
 6 class TrieTree {
 7     let root = TrieNode()
 8 
 9     func insert(_ word:String) {
10         var node: TrieNode? = root
11         for c in word{
12             guard let _node = node else {
13                 continue
14             }
15             if let child = _node.children[c] {
16                 node = child
17             } else {
18                 node = TrieNode()
19                 _node.children[c] = node
20             }
21         }
22         node?.word = word
23     }
24 }
25 
26 
27 class Solution {
28     func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
29         
30         
31         let trie = TrieTree()
32         var record = [[Bool]](repeating:[Bool](repeating:false, count:board[0].count), count:board.count)
33         var result = Set<String>()
34         
35         
36         for word in words {
37             trie.insert(word)
38         }
39         
40         for x in 0..<board.count {
41             for y in 0..<board[0].count {
42                 guard let node = trie.root.children[board[x][y]] else {
43                     continue
44                 }
45                 search(board,&record,node,x,y, &result)
46             }
47         }
48 
49         return Array(result)
50 
51     }
52     
53     
54     func search (_ board: [[Character]],_ record:inout [[Bool]], _ node:TrieNode,_ x:Int, _ y:Int, _ result:inout Set<String>) {
55         guard !record[x][y] else {
56             return
57         }
58 
59         if let word = node.word {
60             result.insert(word)
61         }
62         
63         record[x][y] = true
64         
65         for (x,y) in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)] {
66             guard x < board.count, x >= 0, y < board[0].count, y >= 0, let next = node.children[board[x][y]] else {
67                 continue
68             }
69             search(board,&record,next,x,y, &result)
70         }
71         
72         record[x][y] = false
73     }
74 }

488ms

 1 class Solution {
 2     let directions = [
 3         [0, 1],
 4         [1, 0],
 5         [0, -1],
 6         [-1, 0],
 7     ]
 8     func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
 9         var result = [String]() 
10         guard board.count > 0 && board[0].count > 0 && words.count > 0 else {
11             return result
12         }
13         var wordChars = words.map { Array($0) }
14         var root = TrieNode()
15         for chars in wordChars {
16             buildTree(&root, chars)   
17         }
18         var board = board
19         for row in 0..<board.count {
20             for col in 0..<board[0].count {
21                 doFindWords(&board, &result, row, col, &root)
22             }
23         }
24         return result
25     }
26     
27     private func doFindWords(_ board: inout [[Character]], _ result: inout [String], _ row: Int, _ col: Int, _ node: inout TrieNode) {
28         guard 0 <= row && row < board.count && 0 <= col && col < board[0].count else {
29             return
30         }
31         let char = board[row][col]
32         guard node.next[char] != nil else {
33             return
34         }
35         var node = node.next[char]!
36         if let word = node.getWord() {
37             result.append(word)
38             node.setWord(nil)
39         }
40         board[row][col] = "#"
41         for direction in directions {
42             doFindWords(&board, &result, row + direction[0], col + direction[1], &node)
43         }
44         board[row][col] = char
45     }
46     
47     private func buildTree(_ root: inout TrieNode, _ chars: [Character]) {
48         var node = root
49         for char in chars {
50             if node.next[char] == nil {
51                 node.next[char] = TrieNode()
52             }
53             node = node.next[char]!
54         }
55         node.setWord(String(chars))
56     }
57 }
58 
59 class TrieNode {
60     var next: [Character: TrieNode]
61     var word: String?
62     
63     init() {
64         self.next = [Character: TrieNode]()
65         self.word = nil
66     }
67     
68     func setWord(_ word: String?) {
69         self.word = word
70     }
71     
72     func getWord() -> String? {
73         return word
74     }
75 }

500ms

 1 class Solution {
 2     private class TrieNode {
 3         var children: [TrieNode?]
 4         var word: String?
 5         
 6         init() {
 7             children = [TrieNode?](repeating: nil, count: 26