LeetCode/src/main/java/L0079_WordSearch.java at master · LjyYano/LeetCode · GitHub

History

126 lines (112 loc) · 4.38 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

/**

* https://leetcode.cn/problems/word-search/

* 79. 单词搜索

* 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

* 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中"相邻"单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

* 示例 1：

* 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

* 输出：true

* 示例 2：

* 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

* 输出：true

* 示例 3：

* 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

* 输出：false

* 提示：

* m == board.length

* n = board[i].length

* 1 <= m, n <= 6

* 1 <= word.length <= 15

* board 和 word 仅由大小写英文字母组成

public class L0079_WordSearch {

// 定义四个方向：上、右、下、左

private static final int[][] DIRECTIONS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

public boolean exist(char[][] board, String word) {

if (board == null || board.length == 0 || board[0].length == 0 || word == null || word.isEmpty()) {

return false;

}

int m = board.length;

int n = board[0].length;

boolean[][] visited = new boolean[m][n];

// 从每个格子开始尝试

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (backtrack(board, word, 0, i, j, visited)) {

return true;

}

return false;

}

private boolean backtrack(char[][] board, String word, int index, int row, int col, boolean[][] visited) {

// 如果已经找到了所有字符，返回true

if (index == word.length()) {

return true;

}

// 检查当前位置是否越界或已访问或字符不匹配

if (row < 0 || row >= board.length || col < 0 || col >= board[0].length ||

visited[row][col] || board[row][col] != word.charAt(index)) {

return false;

}

// 标记当前格子为已访问

visited[row][col] = true;

// 向四个方向探索

for (int[] dir : DIRECTIONS) {

int newRow = row + dir[0];

int newCol = col + dir[1];

if (backtrack(board, word, index + 1, newRow, newCol, visited)) {

return true;

}

// 回溯，将当前格子标记为未访问

visited[row][col] = false;

return false;

}

public static void main(String[] args) {

L0079_WordSearch solution = new L0079_WordSearch();

// 测试用例1

char[][] board1 = {

{'A', 'B', 'C', 'E'},

{'S', 'F', 'C', 'S'},

{'A', 'D', 'E', 'E'}

};

String word1 = "ABCCED";

System.out.println("Test case 1: Input board = " + arrayToString(board1) + ", word = \"" + word1 + "\"");

System.out.println("Output: " + solution.exist(board1, word1)); // 应该输出 true

// 测试用例2

String word2 = "SEE";

System.out.println("\nTest case 2: Input board = " + arrayToString(board1) + ", word = \"" + word2 + "\"");

System.out.println("Output: " + solution.exist(board1, word2)); // 应该输出 true

// 测试用例3

String word3 = "ABCB";

System.out.println("\nTest case 3: Input board = " + arrayToString(board1) + ", word = \"" + word3 + "\"");

System.out.println("Output: " + solution.exist(board1, word3)); // 应该输出 false

}

// 辅助方法：将二维字符数组转换为字符串

private static String arrayToString(char[][] board) {

StringBuilder sb = new StringBuilder();

sb.append("[");

for (int i = 0; i < board.length; i++) {

sb.append("[");

for (int j = 0; j < board[i].length; j++) {

sb.append("\"").append(board[i][j]).append("\"");

if (j < board[i].length - 1) {

sb.append(",");

}

sb.append("]");

if (i < board.length - 1) {

sb.append(",");

}

sb.append("]");

return sb.toString();

}

LeetCode/src/main/java/L0079_WordSearch.java at master · LjyYano/LeetCode · GitHub

Expand file tree

Breadcrumbs

L0079_WordSearch.java

Latest commit

History

Breadcrumbs

L0079_WordSearch.java

File metadata and controls