首页 > 试题广场 >

单词搜索

[编程题]单词搜索
  • 热度指数：3318 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出一个二维字符数组和一个单词，判断单词是否在数组中出现，
单词由相邻单元格的字母连接而成，相邻单元指的是上下左右相邻。同一单元格的字母不能多次使用。

数据范围：
0 < 行长度 <= 100
0 < 列长度 <= 100
0 < 单词长度 <= 1000

例如：
给出的数组为["XYZE","SFZS","XDEE"]时，
对应的二维字符数组为：

若单词为"XYZZED"时，应该返回 true，
也即：

若单词为"SEE"时，应该返回 true，
也即：

若单词为"XYZY"时，应该返回 false。
示例1

输入

["XYZE","SFZS","XDEE"],"XYZZED"

输出

true
示例2

输入

["XYZE","SFZS","XDEE"],"SEE"

输出

true
示例3

输入

["XYZE","SFZS","XDEE"],"XYZY"

输出

false
算法知识视频讲解
添加回答
Java
牛客148901号头像 牛客148901号 
import java.util.*;


public class Solution {
    public boolean exist(String[] board, String word, int startI, int startJ, int searchIndex, boolean[][] visited) {
        if (searchIndex == word.length()) {
            return true;
        }
        if (startI < 0 || startI >= board.length || startJ < 0 || startJ >= board[0].length() ||
                visited[startI][startJ] || board[startI].charAt(startJ) != word.charAt(searchIndex)) {
            return false;
        }

        visited[startI][startJ] = true;
        boolean result = exist(board, word, startI + 1, startJ, searchIndex + 1, visited) ||
                exist(board, word, startI - 1, startJ, searchIndex + 1, visited) ||
                exist(board, word, startI, startJ + 1, searchIndex + 1, visited) ||
                exist(board, word, startI, startJ - 1, searchIndex + 1, visited);
        visited[startI][startJ] = false;
        return result;
    }

    public boolean exist(String[] board, String word) {
        if (board == null || board.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 (exist(board, word, i, j, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
}

发表于 2024-05-02 20:27:34 回复(0)
Java
blue&&lan头像 blue&&lan
java字数多，暗箱好操作，dfs避免为void，找到之后才能停，Lmao 
public boolean exist (String[] board, String word) {
        char[][] c=new char[board.length][board[0].length()];
        int[][] a=new int[board.length][board[0].length()];
        for(int k=0;k<board.length;k++){
            c[k]=board[k].toCharArray();
        }
        for(int i=0;i<c.length;i++){
            for(int j=0;j<c[0].length;j++){
                if(c[i][j]==word.charAt(0)){
                    if(Find(c,i,j,word,0,a))return true;
                }
            }
        }
        return false;
    }
    
    boolean Find(char[][] ch,int x,int y,String s,int n,int[][] arr){
        if(n==s.length()){
            return true;
        }
        if(x<0 || y<0)return false;
        if(x>ch.length-1 || y>ch[0].length-1)return false;
        if(arr[x][y]==1)return false;
        if(ch[x][y]!=s.charAt(n)){
            return false;
        }
        n++;
        arr[x][y]=1;
        if(Find(ch,x,y-1,s,n,arr)
           ||Find(ch,x-1,y,s,n,arr)
           ||Find(ch,x+1,y,s,n,arr)
           ||Find(ch,x,y+1,s,n,arr))return true;
        n--;
        arr[x][y]=0;
        return false;
    }


发表于 2022-05-17 19:56:48 回复(0)
Java
菜到不能再菜的那种头像 菜到不能再菜的那种

思路：命里有时终须有，命里无时莫强求。

import java.util.*;
public class Solution {
    public boolean exist(String[] strs, String word) {
        char[][] board = new char[strs.length][strs[0].length()];
        for (int i = 0; i < strs.length; i++) board[i] = strs[i].toCharArray();
        for (int i = 0; i < strs.length; i++) {
            for (int j = 0; j < strs[0].length(); j++) {
                if (dfs(board, word.toCharArray(), i, j, 0)) return true;
            }
        }
        return false;
    }
    public boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if (i >= board.length || i = board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if (k == word.length - 1) return true;
        board[i][j] = '\0';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
}
发表于 2022-03-27 00:44:01 回复(0)
Java
pein531头像 pein531
深度优先搜索，每层都尝试4个方向，有一个方向搜索成功了就表示矩阵中存在这个单词。 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board string字符串一维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    int[] dx = new int[]{-1, 1, 0, 0};
    int[] dy = new int[]{0, 0, -1, 1};
    public boolean exist (String[] board, String word) {
        // write code here
        char[][] grid = new char[board.length][board[0].length()];
        for(int i = 0; i < board.length; i++){
            grid[i] = board[i].toCharArray();
        }
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(word.charAt(0) == grid[i][j]){
                    if(dfs(grid, word, 0, i, j, visited)) return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] grid, String word, int depth, int x, int y, boolean[][] visited) {
        // 所有字符判断完了，返回true
        if(depth == word.length()) {
            return true;
        }
        // 越界或访问过或字符不等，返回false
        if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || visited[x][y] || grid[x][y] != word.charAt(depth)){
            return false;
        }
        // 尝试4个方向，有一个成功就行
        visited[x][y] = true;
        for(int i = 0; i < 4; i++){
            if(dfs(grid, word, depth + 1, x + dx[i], y + dy[i], visited)){
                return true;
            }
        }
        // 回溯
        visited[x][y] = false;
        return false;
    }
}
发表于 2021-12-13 21:13:21 回复(0)
提交观点

问题信息

数组 递归
上传者：牛客301499号
难度：
6条回答 1993浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号