当前位置: 首页 > article >正文

力扣--LCR 129.字母迷宫

题目

字母迷宫游戏初始界面记作 m x n 二维字符串数组 grid,请判断玩家是否能在 grid 中找到目标单词 target。
注意:寻找单词时 必须 按照字母顺序,通过水平或垂直方向相邻的单元格内的字母构成,同时,同一个单元格内的字母 不允许被重复使用 。
在这里插入图片描述
示例 1:

输入:grid = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], target = “ABCCED”
输出:true

示例 2:

输入:grid = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], target = “SEE”
输出:true

示例 3:

输入:grid = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], target = “ABCB”
输出:false

提示:

m == grid.length
n = grid[i].length
1 <= m, n <= 6
1 <= target.length <= 15
grid 和 target 仅由大小写英文字母组成

代码

class Solution {
int n;
int m;
int len;
boolean[][] visited;
public boolean wordPuzzle(char[][] grid, String target) {
this.n = grid.length;
this.m = grid[0].length;
this.len = target.length();
visited = new boolean[n][m];

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(dsf(grid, i, j, target, 0)){
                return true;
            }
        }
    }

    return false;
}
boolean dsf(char[][] grid, int i, int j, String target, int k){
    // 判断是否越界,已经访问过或者不匹配
    if(i < 0 || i >= n || j < 0 || j >= m || grid[i][j] != target.charAt(k)){
        return false;
    }

    if(k == len - 1){
        return true;
    }
    //visited[i][j] = true;
    grid[i][j] = '\n';
    // 四个方向都搜索一下
    boolean res = dsf(grid, i, j + 1, target, k + 1) ||
                  dsf(grid, i + 1, j, target, k + 1) ||
                  dsf(grid, i, j - 1, target, k + 1) ||
                  dsf(grid, i - 1, j, target, k + 1);

    grid[i][j] = target.charAt(k);
    return res;
    // 时间复杂度:mn * 3^len

}
}
时间复杂度:O(3^K * MN) : 最差情况下,需要遍历矩阵中长度为 KK 字符串的所有方案,时间复杂度为 O(3^K);矩阵中共有 MN 个起点,时间复杂度为 O(MN)
空间复杂度:O(k)


http://www.kler.cn/a/444026.html

相关文章:

  • 华为IPD流程6大阶段370个流程活动详解_第一阶段:概念阶段 — 81个活动
  • 网络安全概论——身份认证
  • 拆解一个微型气泵了解工作原理
  • 分布式协同 - 分布式事务_TCC解决方案
  • 3354. 使数组元素等于零
  • JVM性能优化一:初识内存泄露-内存溢出-垃圾回收
  • Go怎么做性能优化工具篇之pprof
  • C# 文件系统I/O操作--File类与FileInfo类
  • 【Tomcat】第三站:注解
  • 两款轻量级数据库SQLite 和 TinyDB,简单!实用!
  • thinkphp5验证码captcha无法显示
  • 字符串类算法
  • Connection lease request time out 问题分析
  • 基于java的CRM客户关系管理系统的设计与实现
  • 计算机必背单词——云计算和虚拟化
  • 数据结构:双向带头循环链表的增删查改
  • 使用Maven打包javaagent.jar
  • 关于解决VScode中python解释器中的库Not Found的问题
  • C# 开发应用篇——C# 基于WPF实现数据记录导出excel详解
  • Unity添加newtonsoft-json
  • 着色器 (三)
  • 游戏《姆吉拉的假面》启动时提示“xinput1_3.dll丢失”怎么办?“xinput1_3.dll丢失”要怎么解决?
  • 三、ubuntu18.04安装docker
  • 【openssl】 version `OPENSSL_3.0.3‘ not found 问题
  • conda-pack迁移虚拟环境
  • 【Qt】qt安装