找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

编程算法题:单词搜索 II(DFS + 回溯)

admin 2019-10-10 06:00 77人围观 C++相关




是新朋友吗?记得先点蓝字关注我哦~


题目描述

给定一个二维网格 board 和一个字典中的单词列表words,找出所有同时在二维网格和字典中出现的单词。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例:

输入:

words =["oath","pea","eat","rain"] and board =

[

 ['o','a','a','n'],

 ['e','t','a','e'],

 ['i','h','k','r'],

 ['i','f','l','v']

]
输出: ["eat","oath"]
解决思路

使用深度优先搜索(DFS)和回溯的思想实现。关于判断元素是否使用过,可用一个二维数组mark对使用过的元素做标记。
首先遍历board的所有元素,先找到和word第一个字母相同的元素,然后进入递归流程。假设这个元素的坐标为 (i, j),进入递归流程前,先记得把该元素打上使用过的标记:mark[i][j] = true。打完标记后,进入了递归流程,递归流程主要做了这么几件事:1)从 (i, j) 出发,朝它的上下左右试探,看看它周边的这四个元素是否能匹配word的下一个字母。如果匹配到了,带着该元素继续进入下一个递归,如果都匹配不到,则返回false。2)当word的所有字母都完成匹配后,整个流程返回true。
以此类推,将满足条件的word存放到tmp(集合类型,找到相同的结果,只需返回其中一个即可),最后再转换成ArrayList类型返回。

Java代码实现

    public class Solution {public List<String>findWords(char[][] board, List<String>words) { Set<String> tmp = new HashSet<>();int row = board.length;int col = board[0].length; boolean marked[][] = new boolean[row][col];
    for (String word : words) {for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {if (dfs(i, j, 0, board, word, marked)){ tmp.add(word); } } }
    marked = new boolean[row][col]; }
    returnnew ArrayList<>(tmp); }
    private boolean isInArea(int x,int y, char[][]board) {return x>= 0 && x < board.length && y >=0 &&y < board[0].length; }
    private boolean dfs(int x,int y, int start, char[][] board, String word, boolean[][]marked) {if (start== word.length() - 1) {return board[x][y]== word.charAt(start); }
    int[][]direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};if (board[x][y] == word.charAt(start)) { marked[x][y] = true;
    for (int i = 0; i < 4; i++) {int newX= x + direction[i][0];int newY = y + direction[i][1];if (isInArea(newX, newY, board) && !marked[newX][newY]) {if (dfs(newX, newY, start+ 1, board, word, marked)) {returntrue; } } }
    marked[x][y] = false; }
    returnfalse; }
    publicstaticvoidmain(String[]args) { Solution solution = new Solution();char[][] board = {{'o', 'a', 'a', 'n'},{'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'}}; List<String> words = new ArrayList<>(); words.add("oath"); words.add("pea"); words.add("eat"); words.add("rain"); System.out.println(solution.findWords(board, words)); }}

    推荐阅读:

    5分钟理解DFS算法

    5分钟理解一致性哈希算法

    程序员必须知道的十种算法(上)

    程序员必须知道的十种算法(下)

    看完本文有收获?请分享给更多的人

    在技术成长的路上,让我们一起进步吧




    ----------------------------------------------------------------------------------------------------------------------
    我们尊重原创,也注重分享,文章来源于微信公众号:码农之屋,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
    ----------------------------------------------------------------------------------------------------------------------

    鲜花

    握手

    雷人

    路过

    鸡蛋

    yafeilinux和他的朋友们微信公众号二维码

    微信公众号

    专注于Qt嵌入式Linux开发等。扫一扫立即关注。

    Qt开源社区官方QQ群二维码

    QQ交流群

    欢迎加入QQ群大家庭,一起讨论学习!

    我有话说......