612. Word on the Board
A tile game lays lowercase letters out in a rectangular grid board. A player spells word by choosing a starting tile and then moving one step at a time to a tile directly above, below, left or right of the current one. The same tile may not be used twice in one spelling.
Return true if word can be spelled this way and false otherwise. Failing branches must be abandoned as early as possible: stop as soon as a tile does not match, and give up at once when the board does not even contain enough copies of every letter in word.
Example 1
- Input:
- board = [["w","x","y"],["z","a","b"],["c","d","e"]]word = "abe"
- Output:
- true
- Explanation:
Start at
a, go right tob, then down toe: all three tiles are adjacent and distinct.
Example 2
- Input:
- board = [["a","b"],["c","d"]], word = "abcd"
- Output:
- false
- Explanation:
After
aandbthe path would need to jump diagonally frombtoc, which is not allowed, so the word cannot be spelled.
Example 3
- Input:
- board = [["a","a"],["a","a"]], word = "aaaaa"
- Output:
- false
- Explanation:
The board only has four tiles, so a five-letter word cannot fit.
Constraints
- 1 ≤
board.length,board[i].length≤ 8 - 1 ≤
word.length≤ 40 - The board and the word contain only lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(m * n * 3^L)
- Space
- O(L)