[アルゴリズム]LeetCode-Word Search
14333 ワード
LeetCode - Word Search
問題の説明
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
I/O例
Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Example 2:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
せいげんじょうけん
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.
Solution
[戦略]
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.
import java.util.Arrays;
class Solution {
public boolean exist(char[][] board, String word) {
boolean[][] visits = new boolean[board.length][board[0].length];
for (boolean[] visit : visits) {
Arrays.fill(visit, false);
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
// System.out.println("i , j :"+ i+ " : "+j);
if (backtracking(board, visits, i, j, word, 0)) {
return true;
}
}
}
return false;
}
public boolean backtracking(char[][] board, boolean[][] visits, int i, int j, String word, int len) {
if (board[i][j] == word.charAt(len)) {
if (word.length() == len + 1) {
return true;
}
visits[i][j] = true;
boolean up = i <= 0 || visits[i - 1][j] ? false : backtracking(board, visits, i - 1, j, word, len + 1);
boolean down = i >= board.length - 1 || visits[i + 1][j] ? false
: backtracking(board, visits, i + 1, j, word, len + 1);
boolean left = j <= 0 || visits[i][j - 1] ? false : backtracking(board, visits, i, j - 1, word, len + 1);
boolean right = j >= board[0].length - 1 || visits[i][j + 1] ? false
: backtracking(board, visits, i, j + 1, word, len + 1);
visits[i][j] = false;
return up || down || left || right;
}
return false;
}
}
Reference
この問題について([アルゴリズム]LeetCode-Word Search), 我々は、より多くの情報をここで見つけました https://velog.io/@jerry92/알고리즘-LeetCode-Word-Searchテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol