★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★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 lettersa-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 组成。 提示:
-
- 你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？
- 如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 。
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 () 70 71 72 for word in words { 73 trie.insert(word) 74 } 75 76 for x in 0.. 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 ) { 98 guard x < board.count, x >= 0, y < board[0].count, y >= 0, !record[x][y] else { 99 return100 }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] = true109 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] = false127 }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() - lowerLetterUnicodeStart15 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 = nil20 }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] = char27 }28 29 for i in 0.. TrieNode {38 let root = TrieNode()39 for word in words {40 var point = root41 for char in word {42 let charIndex = char.char2Int() - lowerLetterUnicodeStart43 if point.next[charIndex] == nil { point.next[charIndex] = TrieNode() }44 point = point.next[charIndex]!45 }46 point.word = word47 }48 return root49 }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 result14 }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 result22 }23 24 func dfs(_ board: inout [[Character]], _ i: Int, _ j: Int, _ trie: TrieNode, _ result: inout [String]) {25 var trie = trie26 27 if board[i][j] == "*" || trie.children[board[i][j]] == nil {28 return29 }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] = cur45 return46 }47 }48 49 class Trie {50 public var root = TrieNode()51 52 public func insert(_ word: String) {53 var head = root54 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 = word63 }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? = root11 for c in word{12 guard let _node = node else {13 continue14 }15 if let child = _node.children[c] {16 node = child17 } else {18 node = TrieNode()19 _node.children[c] = node20 }21 }22 node?.word = word23 }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 ()34 35 36 for word in words {37 trie.insert(word)38 }39 40 for x in 0.. ) {55 guard !record[x][y] else {56 return57 }58 59 if let word = node.word {60 result.insert(word)61 }62 63 record[x][y] = true64 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 continue68 }69 search(board,&record,next,x,y, &result)70 }71 72 record[x][y] = false73 }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 result12 }13 var wordChars = words.map { Array($0) }14 var root = TrieNode()15 for chars in wordChars {16 buildTree(&root, chars) 17 }18 var board = board19 for row in 0.. String? {73 return word74 }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) 8 word = nil 9 }10 }11 12 func findWords(_ board: [[Character]], _ words: [String]) -> [String] {13 var result = [String]()14 let trieRoot = buildTrie(from: words)15 let rows = board.count, cols = board[0].count16 let rowSeen = [Bool](repeating: false, count: cols)17 var seen = [[Bool]](repeating: rowSeen, count: rows)18 for r in 0.. TrieNode {27 let root = TrieNode()28 for word in words {29 var node: TrieNode? = root30 for char in word.unicodeScalars {31 let index = Int(char.value) - 9732 if node?.children[index] == nil {33 node?.children[index] = TrieNode()34 }35 node = node?.children[index]36 }37 node?.word = word38 }39 return root40 }41 42 private func search(_ board: [[Character]], _ seen: inout [[Bool]], _ r: Int, _ c: Int, _ node: TrieNode) -> [String] {43 guard 0 <= r && r < board.count && 0 <= c && c < board[0].count && !seen[r][c] else {44 return []45 }46 let childNodeIndex = Int(board[r][c].unicodeScalars.first!.value) - 9747 guard let childNode = node.children[childNodeIndex] else {48 return []49 }50 var result = [String]()51 if let word = childNode.word {52 result.append(word)53 childNode.word = nil54 }55 seen[r][c] = true56 result.append(contentsOf: search(board, &seen, r + 1, c, childNode))57 result.append(contentsOf: search(board, &seen, r - 1, c, childNode))58 result.append(contentsOf: search(board, &seen, r, c + 1, childNode))59 result.append(contentsOf: search(board, &seen, r, c - 1, childNode))60 seen[r][c] = false61 return result62 }63 } 524ms
1 class Solution { 2 3 class WordNode { 4 var children = [WordNode]() 5 var isWord = false 6 var char : Character 7 init(_ c : Character) { 8 char = c 9 }10 }11 12 func addWord(_ word : String, _ node : WordNode){13 var lastNode = node14 let wordArr = Array(word)15 for c in wordArr {16 var find = false17 for sub in lastNode.children where sub.char == c {18 find = true19 lastNode = sub20 }21 22 if !find {23 let nc = WordNode(c)24 lastNode.children.append(nc)25 lastNode = nc26 }27 }28 lastNode.isWord = true29 }30 31 func findWords(_ board: [[Character]], _ words: [String]) -> [String] {32 33 let root = WordNode(".")34 35 for word in words {36 addWord(word, root)37 }38 39 var curr = ""40 var res = Set ()41 var visited = Array(repeating: Array(repeating: false, count: board[0].count), count: board.count)42 for i in 0.. , _ curr : inout String) {52 53 54 55 56 let c = board[m][n]57 var sub : WordNode?58 for child in node.children where child.char == c {59 sub = child60 curr += String(sub!.char)61 }62 if sub == nil {63 return64 }65 66 67 if sub!.isWord {68 res.insert(curr)69 }70 71 visited[m][n] = true72 if m+1 < board.count && !visited[m+1][n] {73 find(board, &visited, m+1, n, sub!, &res, &curr)74 }75 if n+1 < board[0].count && !visited[m][n+1] {76 find(board, &visited, m, n+1, sub!, &res, &curr)77 }78 if m > 0 && !visited[m-1][n] {79 find(board, &visited, m-1, n, sub!, &res, &curr)80 }81 if n > 0 && !visited[m][n-1] {82 find(board, &visited, m, n-1, sub!, &res, &curr)83 }84 visited[m][n] = false85 curr.popLast()86 }87 } 548ms
1 class Node: CustomStringConvertible { 2 var index: Int 3 var char: Character 4 var children = [Node]() 5 6 public var description: String { return "Node: \(index) -> \(char) & \(children.count)" } 7 8 init(_ i: Int, _ c: Character) { 9 index = i 10 char = c 11 } 12 } 13 14 extension String { 15 func charAt(_ i: Int) -> Character { 16 return self[index(startIndex, offsetBy: i)] 17 } 18 } 19 20 class Solution { 21 let abc = (97...122).map({Character(UnicodeScalar($0))}) 22 23 func findWords(_ board: [[Character]], _ words: [String]) -> [String] { 24 25 var ans = Set () 26 var m = board.count 27 var n = board[0].count 28 var root = [[Node]]() 29 30 for i in 0.. 0 { 40 root[i][j].children.append(root[i - 1][j]) 41 } 42 if i < m - 1 { 43 root[i][j].children.append(root[i + 1][j]) 44 } 45 if j > 0 { 46 root[i][j].children.append(root[i][j - 1]) 47 } 48 if j < n - 1 { 49 root[i][j].children.append(root[i][j + 1]) 50 } 51 } 52 } 53 54 // print(root) 55 56 for word in words { 57 var visited = [Bool](repeating: false, count: m * n) 58 var index = 0 59 60 if (search(root, &visited, String(word.reversed()), &index)) { 61 ans.insert(word) 62 } 63 } 64 65 return Array(ans) 66 } 67 68 func search(_ root: [[Node]], _ visited: inout [Bool], _ word: String, _ index: inout Int) -> Bool { 69 if index == word.count { 70 return true 71 } 72 73 let charToFind = word.charAt(index) 74 var validNodes = [Node]() 75 76 for row in root { 77 for node in row { 78 if node.char == charToFind { 79 if !visited[node.index] { 80 validNodes.append(node) 81 } 82 } 83 } 84 } 85 86 // print(validNodes) 87 88 for node in validNodes { 89 visited[node.index] = true 90 index += 1 91 if searchInWord(node, &visited, word, &index) { 92 return true 93 } 94 index -= 1 95 visited[node.index] = false 96 } 97 98 return false 99 }100 101 func searchInWord(_ root: Node, _ visited: inout [Bool], _ word: String, _ index: inout Int) -> Bool {102 if index == word.count {103 return true104 }105 106 let charToFind = word.charAt(index)107 var validNodes = [Node]()108 109 for node in root.children {110 if node.char == charToFind && !visited[node.index] {111 validNodes.append(node)112 }113 }114 115 for node in validNodes {116 visited[node.index] = true117 index += 1118 if searchInWord(node, &visited, word, &index) {119 return true120 }121 index -= 1122 visited[node.index] = false123 }124 125 return false126 }127 } 684ms
1 class Solution { 2 func findWords(_ board: [[Character]], _ words: [String]) -> [String] { 3 //check if board or word is empty 4 if board.count == 0 || board[0].count == 0 || words.count == 0 { 5 return [] 6 } 7 var rowCount = board.count 8 var colCount = board[0].count 9 10 //convert word to a prefix map11 var isWordMap: [String: Bool] = getWordMap(words)12 13 //2D array to track visited location14 var visited = Array(repeating: Array(repeating: false, count: colCount), count: rowCount)15 16 //result: use set to remove duplicate 17 var wordSet: Set = Set ()18 19 for i in 0 ..< rowCount {20 for j in 0 ..< colCount {21 visited[i][j] = true22 //use word map to find words that be constrcuted from letters23 findWord(i, j, String(board[i][j]), isWordMap, &visited, &wordSet, board)24 visited[i][j] = false25 }26 }27 return Array(wordSet)28 }29 30 private func getWordMap(_ words: [String]) -> [String: Bool] {31 var wordMap = [String: Bool]() 32 for word in words {33 for i in 1 ... word.count {34 let subString = String(word.prefix(i))35 if wordMap[subString] == nil {36 wordMap[subString] = false37 }38 }39 wordMap[word] = true40 }41 return wordMap42 }43 44 private func findWord(_ colIndex: Int, _ rowIndex: Int, 45 _ word: String, _ wordMap: [String: Bool],46 _ visited: inout [[Bool]], _ res: inout Set ,47 _ charBoard: [[Character]]) {48 //wordMap doesn't contain the prefix, exit49 if wordMap[word] == nil {50 return51 }52 53 //prefix is word, add to result54 if wordMap[word]! {55 res.insert(word)56 }57 58 //4 directions59 let dirX = [0, 0, 1, -1]60 let dirY = [1, -1, 0, 0]61 62 for i in 0 ..< 4 {63 let newCol = colIndex + dirX[i]64 let newRow = rowIndex + dirY[i]65 66 //check bounds and if it is visited67 if !inDict(newCol, newRow, charBoard.count, charBoard[0].count) || visited[newCol][newRow] {68 continue69 }70 71 visited[newCol][newRow] = true72 //keep checking if word map contains new string73 findWord(newCol, newRow, word + String(charBoard[newCol][newRow]),74 wordMap, &visited, &res, charBoard)75 visited[newCol][newRow] = false76 }77 }78 79 private func inDict(_ colIndex: Int, _ rowIndex: Int, _ colMax: Int, _ rowMax: Int) -> Bool {80 return colIndex >= 0 && rowIndex >= 0 && colIndex < colMax && rowIndex < rowMax81 }82 }