力扣0079单词搜索

本文主要是介绍力扣0079单词搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

单词搜索

难度：中等

题目描述：

给定一个 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

题解：

根据题目可得需要用到回溯算法
遍历表格内的每一个元素，如果满足要求即可回溯，最终得到结果，以下为具体步骤:

• 定义两个方向数组moveX和moveY
• 如果当前位置的元素和单词中的元素内容不相同，返回false
• 如果遍历到单词的最后一个元素，返回true
• 将当前位置设置为true，并进行循环：
  • 新的方向为当前方向加上第i次循环中moveX[i]和move[Y]的值
  • 如果新的方向均大于零并且移动的下一次元素位置不超过二维数组边界并且将要遍历的元素没有使用过，那么就进行回溯，将新的移动位置传入到回溯，并将判断的单词元素下标加一
  • 如果回溯结束之后满足条件，返回ture
  • 如果循环结束之后没有最终满足，对操作进行回头，即将当前位置设为未使用并返回false
• 遍历每一个元素，对其都进行回溯，如果其中的元素在回溯中最后返回true，则返回true
• 如果所有元素都不满足条件，则返回false

最后的结果即为题目答案

想法代码

class Solution
{readonly int[] desX = new int[] { 1, -1, 0, 0 };readonly int[] desY = new int[] { 0, 0, 1, -1 };public static void Main(String[] args){char[][] board ={new[] { 'A', 'B', 'C', 'E' },new[] { 'S', 'F', 'C', 'S' },new[] { 'A', 'D', 'E', 'E' }};string word = "ABCB";Solution solution = new Solution();bool res = solution.Exist(board, word);Console.WriteLine(res);}bool DFS(int x, int y, string word, int index, char[][] board, bool[,] used){if (word[index] != board[x][y]) return false;if (index == word.Length - 1) return true;used[x, y] = true;for (int i = 0; i < 4; i++){int newX = x + desX[i];int newY = y + desY[i];if (newX >= 0 && newY >= 0 && newX < board.Length && newY < board[0].Length && used[newX, newY] != true){if (DFS(newX, newY, word, index + 1, board, used)) return true;}}used[x, y] = false;return false;}public bool Exist(char[][] board, string word){bool[,] used = new bool[board.Length, board[0].Length];for (int i = 0; i < board.Length; i++){for (int j = 0; j < board[i].Length; j++){if (board[i][j] == word[0]){if (DFS(i, j, word, 0, board, used)) return true;}}}return false;}
}

这篇关于力扣0079单词搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---