客服电话
APP下载
迪恩网络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 = Note: 给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。 示例: 输入: words = 说明: 提示:
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 |
请发表评论