Problem Statement
Given a 2D board and a word, find if the word exists in the grid.
The word can 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.
For example,
Given board =
|
1 2 3 4 5 |
[ ["ABCE"], ["SFCS"], ["ADEE"] ] |
word =
"ABCCED", -> returns
true,
word =
"SEE", -> returns
true,
word =
"ABCB", -> returns
false.
Original LeetCode problem page
My Solution in Swift
Recursive version:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
func recursiveExist(var board: [[UInt8]], var word: [UInt8]) -> Bool { if word.count == 0 { return true } var prevPoses: [Int:Void] = [:] // Use Dictionary as a hashset for var i = 0; i < board.count; ++i { for var j = 0; j < board[0].count; ++j { if _recursiveExist((j, i), &board, &word, 0, &prevPoses) { return true } } } return false } |
Iterative version:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
func iterativeExist(board: [[UInt8]], word: [UInt8]) -> Bool { if word.count == 0 { return true } var prevPoses: [Int:Void] = [:] // Use Dictionary as a hashset struct Frame { var pos: (x: Int, y: Int) var dir: Int } var stack: [Frame] = [] var currWordPos = 0 var pos: (x: Int, y: Int) = (-1, -1) var dir = 0 func popLastFrame() { let currFrame = stack.removeLast() pos = currFrame.pos prevPoses[combine(pos)] = nil dir = currFrame.dir + 1 --currWordPos } func searchPos(newPos: (Int, Int), oldDir: Int) { prevPoses[combine(pos)] = () stack.append(Frame(pos: pos, dir: oldDir)) pos = newPos dir = 0 ++currWordPos } for var i = 0; i < board.count; ++i { for var j = 0; j < board[0].count; ++j { pos = (j, i) search: while true { if prevPoses[combine(pos)] != nil || board[pos.y][pos.x] != word[currWordPos] { if stack.count == 0 { break search } else { popLastFrame() } } if currWordPos == word.count - 1 { return true } switch dir { case 0: if pos.y > 0 { searchPos((pos.x, pos.y - 1), 0) continue search } fallthrough case 1: if pos.x < board[0].count - 1 { searchPos((pos.x + 1, pos.y), 1) continue search } fallthrough case 2: if pos.y < board.count - 1 { searchPos((pos.x, pos.y + 1), 2) continue search } fallthrough case 3: if pos.x > 0 { searchPos((pos.x - 1, pos.y), 3) continue search } fallthrough default: if stack.count == 0 { break search } else { popLastFrame() } } } dir = 0 } } return false } |
The recursive version runs twice as fast as the iterative version (57 ms vs 116 ms). In the iterative implementation, I used a stack array to record traversed node information so that the program can later backtrack if needed. This doesn’t work as efficient as the same kind of automatic information book keeping in recursion.
Try It Yourself
1: each links to a blog post of mine that is dedicated to the problem
2: total execution time of a solution on my MacBook Pro (Late 2013, 2.6 GHz Intel Core i7, 16 GB 1600 MHz DDR3). Each solution is compiled with following command:
$ swiftc -O -sdk `xcrun --show-sdk-path --sdk macosx` json.swift main.swift -o mySolution
The total execution time is the average of 10 runs.
3: these test cases are semi-automatically :P retrieved from LeetCode Online Judge system and are kept in JSON format
4: each Xcode project includes everything (my Swift solution to a problem, its JSON test cases and a driver code to test the solution on those test cases)
| Problem1 | Time2 | Test Cases3 | My Xcode Project4 |
| Word Search | 57.457ms |