本文主要是介绍【LeetCode: 212. 单词搜索 II - dfs】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
🚀 算法题 🚀 |
🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯
🚀 算法题 🚀 |
🍔 目录
- 🚩 题目链接
- ⛲ 题目描述
- 🌟 求解思路&实现代码&运行结果
- ⚡ dfs
- 🥦 求解思路
- 🥦 实现代码
- 🥦 运行结果
- 💬 共勉
🚩 题目链接
- 212. 单词搜索 II
⛲ 题目描述
给定一个 m x n 二维字符网格 board 和一个单词(字符串)列表 words, 返回所有二维网格上的单词 。
单词必须按照字母顺序,通过 相邻的单元格 内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例 1:
输入:board = [[“o”,“a”,“a”,“n”],[“e”,“t”,“a”,“e”],[“i”,“h”,“k”,“r”],[“i”,“f”,“l”,“v”]], words = [“oath”,“pea”,“eat”,“rain”]
输出:[“eat”,“oath”]
示例 2:
输入:board = [[“a”,“b”],[“c”,“d”]], words = [“abcb”]
输出:[]
提示:
m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一个小写英文字母
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同
🌟 求解思路&实现代码&运行结果
⚡ dfs
🥦 求解思路
- 枚举每一个起点,通过dfs上下左右去寻找words数组中的字符串,如果在,就添加,如果不在,就结束,继续寻找,找到所有的答案加入到最终的数组中。
- 有了基本的思路,接下来我们就来通过代码来实现一下。
🥦 实现代码
class Solution {public List<String> findWords(char[][] board, String[] words) {List<String> ans = new ArrayList<>();Set<String> set = new HashSet<>();for (String s : words)set.add(s);int m = board.length, n = board[0].length;boolean[][] map = new boolean[m][n];StringBuilder sb = new StringBuilder();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {dfs(i, j, m, n, board, set, map, sb, ans);}}return ans;}public void dfs(int i, int j, int m, int n, char[][] board, Set<String> set, boolean[][] map,StringBuilder sb, List<String> ans) {if (i < 0 || i >= m || j < 0 || j >= n || map[i][j] || sb.length() > 10)return;map[i][j] = true;sb.append(board[i][j]);if (set.contains(sb.toString())) {ans.add(sb.toString());set.remove(sb.toString());}dfs(i - 1, j, m, n, board, set, map, sb, ans);dfs(i, j + 1, m, n, board, set, map, sb, ans);dfs(i + 1, j, m, n, board, set, map, sb, ans);dfs(i, j - 1, m, n, board, set, map, sb, ans);sb.deleteCharAt(sb.length() - 1);map[i][j] = false;}
}
🥦 运行结果
💬 共勉
最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉! |
这篇关于【LeetCode: 212. 单词搜索 II - dfs】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!