Search for a Word in a 2D Board
Given a rectangular grid of letters and a word, determine whether the word can be formed within the grid.
Consecutive letters of the word must come from horizontally or vertically adjacent cells. A cell cannot be used more than once while forming the same word.
Board Representation
The board is represented as a list of strings. Each string contains one row of letters separated by commas. For example, "A,B,C" represents a row containing the letters A, B, and C.
Method Signature
boolean exist(List<String> board, String word)
board contains the rows of the rectangular letter grid.word is the word to search for.- Return
true if the word can be formed according to the adjacency and cell-reuse rules; otherwise, return false.
Constraints
1 ≤ board.size() ≤ 61 ≤ number of letters in each row ≤ 6- Every row contains the same number of letters.
1 ≤ word.length() ≤ 15- The board and
word contain only uppercase or lowercase English letters.
- A cell may be visited at most once while constructing one occurrence of the word.
- Diagonal cells are not considered adjacent.
Examples
Example 1
exist(board = List.of("C,A,T", "D,O,G", "R,A,T"), word = "CAT")
Output: true
The letters C, A, and T appear in horizontally adjacent cells in the first row.
Example 2
exist(board = List.of("A,B,C", "H,G,D", "I,F,E"), word = "ABCDEFGHI")
Output: true
The word follows a continuous path through horizontally and vertically neighboring cells without reusing any cell.
Example 3
exist(board = List.of("A,B,C"), word = "ABA")
Output: false
Forming the word would require using the only cell containing A twice, which is not allowed.