|
| 1 | +/** |
| 2 | + * Question Link: https://leetcode.com/problems/word-search-ii/ |
| 3 | + */ |
| 4 | + |
| 5 | +classSolution{ |
| 6 | +classTrieNode{ |
| 7 | +varchildren=[Character: TrieNode]() |
| 8 | +varword:String="" |
| 9 | +} |
| 10 | + |
| 11 | +func findWords(_ board:[[Character]], _ words:[String])->[String]{ |
| 12 | +varanswer=[String]() |
| 13 | +letroot=buildTrie(words) |
| 14 | + |
| 15 | +varboard= board |
| 16 | + |
| 17 | +forrowin0..<board.count{ |
| 18 | +forcolin0..<board[0].count{ |
| 19 | +if root.children[board[row][col]]!=nil{ |
| 20 | +dfs(row, col, root,&board,&answer) |
| 21 | +} |
| 22 | +} |
| 23 | +} |
| 24 | + |
| 25 | +return answer |
| 26 | +} |
| 27 | + |
| 28 | +func buildTrie(_ words:[String])->TrieNode{ |
| 29 | +letroot=TrieNode() |
| 30 | +forwordin words{ |
| 31 | +varcurrent= root |
| 32 | + |
| 33 | + word.forEach{ |
| 34 | +if current.children[$0]==nil{ |
| 35 | + current.children[$0]=TrieNode() |
| 36 | +} |
| 37 | + current= current.children[$0]! |
| 38 | +} |
| 39 | + current.word= word |
| 40 | +} |
| 41 | + |
| 42 | +return root |
| 43 | +} |
| 44 | + |
| 45 | +func getInBoardChild(_ x:Int, _ y:Int,_ board:[[Character]],_ root:TrieNode)->TrieNode?{ |
| 46 | +if0..<board[0].count~= x &&0..<board.count~= y &&board[y][x]!="."{ |
| 47 | +return root.children[board[y][x]] |
| 48 | +} |
| 49 | +returnnil |
| 50 | +} |
| 51 | + |
| 52 | +func dfs( _ y:Int,_ x:Int,_ root:TrieNode,_ board:inout[[Character]],_ answer:inout[String]){ |
| 53 | +guardlet child=getInBoardChild(x, y, board, root)else{return} |
| 54 | + |
| 55 | +letchar=board[y][x] |
| 56 | +board[y][x]="." |
| 57 | + |
| 58 | +if !child.word.isEmpty{ |
| 59 | + answer.append(child.word) |
| 60 | + child.word="" |
| 61 | +} |
| 62 | + |
| 63 | +fordin[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]{ |
| 64 | +dfs(d.1,d.0, child,&board,&answer) |
| 65 | +} |
| 66 | + |
| 67 | +board[y][x]= char |
| 68 | +} |
| 69 | +} |