首页 > 其他分享 >#yyds干货盘点# LeetCode面试题:单词搜索

#yyds干货盘点# LeetCode面试题:单词搜索

时间:2023-04-17 18:36:48浏览次数:36  
标签:yyds 面试题 word int boolean board visited true LeetCode

1.简述:

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

2.代码实现:

class Solution {
    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        if (board[i][j] != s.charAt(k)) {
            return false;
        } else if (k == s.length() - 1) {
            return true;
        }
        visited[i][j] = true;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;
        for (int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                if (!visited[newi][newj]) {
                    boolean flag = check(board, visited, newi, newj, s, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }
}

标签:yyds,面试题,word,int,boolean,board,visited,true,LeetCode
From: https://blog.51cto.com/u_15488507/6195822

相关文章

  • 2-211-(LeetCode-470) 用 Rand7() 实现 Rand10()
     1.题目 https://leetcode.cn/problems/implement-rand10-using-rand7/submissions/425373186/ 2.解法 classSolutionextendsSolBase{publicintrand10(){inttemp=40;while(temp>=40){temp=(rand7()-1)*7......
  • 2-209-(LeetCode-121) 买卖股票的最佳时机
     1.题目 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/121. 买卖股票的最佳时机 2.解法2.1解法一:动态规划  2.2解法二:非动态规划 if(prices.length<2){return0;}intmin=prices[0];......
  • 2-207-通过(LeetCode-509)熟悉动态规划的解题步骤
    1.题目 运态规划的定义   动态规划的解题步骤  2.解法2.1递归 publicstaticintfibonacci(intn){if(n==0){return0;}if(n==1){return1;}returnfibonacci(n-1)+fibonacci(n-2);}2.2运态规划+递归......
  • leetcode:最小栈
    问题描述设计一个支持push,pop,top操作,并能在常数时间内检索到最小元素的栈。实现MinStack类:MinStack()初始化堆栈对象。voidpush(intval)将元素val推入堆栈。voidpop()删除堆栈顶部的元素。inttop()获取堆栈顶部的元素。intgetMin()获取堆栈中的最小元素。......
  • 从一道面试题来学习前台进程和后台进程、孤儿进程和僵尸进程
    1、面试题介绍以前面试,面试官问了一个问题,大意是:我们在终端中,通过执行pythonmain.py命令,会启动一台前台进程直到程序结束。现在我还是想通过执行pythonmain.py,启动一个后台进程,让后台进程运行我们的业务逻辑。这个时候应该怎么做呢?回答上面这道题,需要先了解什么是前台......
  • LeetCode Top100: 爬楼梯 (python)
     假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 示例1:输入:n=2输出:2解释:有两种方法可以爬到楼顶。1.1阶+1阶2.2阶示例2:输入:n=3输出:3解释:有三种方法可以爬到楼顶。1.1阶+1......
  • leetcode160-相交链表
    leetcode160方法一:哈希表思路:先创建一个unordered_set,存放ListNode*类型的变量先遍历其中一个链表,把所有节点的指针放在set中再遍历另一个链表,查找是否存在一个节点已经在set中,如果存在则说明这是它们的相交节点的指针,返回这个指针,如果不存在则说明不存在相交节点,......
  • LeetCode-Top100: 有效的括号 (python)
     给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 示例1:输入:s="()"输出:true示例 2:输入:s="()[]{}"输......
  • LeetCode-Top100:两数之和(python)
     给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。 示例1:输入:nums=......
  • leetcode_打卡5
    leetcode_打卡5题目:345.反转字符串中的元音字母思路:双指针classSolution{publicStringreverseVowels(Strings){intn=s.length();char[]arr=s.toCharArray();inti=0;intj=n-1;while(i<j){while(i<n&&!yua......