Word Search Eight Directions
Given a rectangular board of uppercase English letters and a word, determine whether the word can be found in the board. The word must be formed by starting from any cell and then moving in one fixed direction.
From a cell, movement is allowed in any of the 8 directions: left, right, up, down, and the 4 diagonals. After the direction is chosen for the next matched character, all remaining characters must continue in that same direction.
Class
Word Search
WordSearch()
- Creates an object that can check whether a word exists in the board.
Methods
Exists
boolean exists(List<String> board, String word)
- Returns
true if word can be found in the board using one fixed direction.
- Returns
false otherwise.
- Each string in
board represents one row of the board.
- All rows have the same length.
Direction Rules
- The first character of
word may start from any cell.
- The next character may be matched in any one of the 8 directions.
- Once a direction is chosen, every later character must continue in that same direction.
- A direction cannot change while matching the same word.
- If
word has length 1, it exists if any board cell contains that character.
Constraints
1 ≤ board.size() ≤ 2001 ≤ board.get(i).length() ≤ 2001 ≤ word.length() ≤ 40,000board contains only uppercase English letters.word contains only uppercase English letters.- All rows in
board have equal length.
- No parameter value will be
null.
Examples
Example 1
exists(board = List.of("AXMY", "BGDF", "CEHL"), word = "ABC")
- Output:
true
- Explanation: The word is found vertically downward from
A to B to C.
Example 2
exists(board = List.of("ABCD", "EFGH", "IJKL", "MNOP"), word = "AFKP")
- Output:
true
- Explanation: The word is found diagonally downward-right from
A to F to K to P.
Example 3
exists(board = List.of("ABCD", "EFGH", "IJKL"), word = "ABF")
- Output:
false
- Explanation:
A to B moves right, but B to F moves down, so the direction changes.
Example 4
exists(board = List.of("QWE", "RTY", "UIO"), word = "T")
- Output:
true
- Explanation: A single-character word exists because
T is present in the board.
Example 5
exists(board = List.of("CAT", "DOG", "PIG"), word = "COW")
- Output:
false
- Explanation: The word cannot be matched from any starting cell in one fixed direction.