E-找单词(100p)

刷题笔记合集🔗

找单词

问题描述

给定一个字符串和一个二维字符数组,要求判断该字符串是否存在于数组中。如果存在,则按字符串字符顺序输出每个字符所在单元格的位置下标字符串;如果找不到则返回 "N"。搜索路径必须按照字符串字符顺序,且只能在水平或垂直相邻的单元格中移动。同一个单元格内的字符不能重复使用。假设在数组中最多只存在一个可能的匹配。

输入格式

第一行是一个整数 ,表示二维数组的行数和列数。

接下来的 行为一个由大写字符组成的二维数组,字符之间用逗号分隔。

最后一行为待查找的字符串,由大写字符组成。

二维数组的大小为 ,其中

单词长度为 ,其中

输出格式

如果能找到该字符串,输出每个位置的下标,并用逗号分隔。

否则,输出 "N"。

样例输入

4
A,C,C,F
C,D,E,D
B,E,S,S
F,E,C,A
ACCESS

样例输出

0,0,0,1,0,2,1,2,2,2,2,3

样例解释

在二维数组中找到字符串 "ACCESS" 的路径,按顺序输出各字符的下标。

数据范围

二维数组的大小为 ,其中

单词长度为 ,其中

题解

为了解决这个问题,我们需要在一个二维字符数组中搜索一个给定的字符串,找到该字符串后输出每个字符的坐标。使用深度优先搜索(DFS)来实现这一目标。DFS 通过递归搜索相邻的单元格,检查当前路径是否匹配目标字符串。

在实现中,我们会从每个可能的起始点开始,进行 DFS 搜索,并在每一步记录当前字符的坐标。如果找到了完整的字符串,就输出路径;否则,继续搜索直到找完所有可能的起始点。如果最终没有找到匹配的路径,就输出 "N"。参考代码

  • Python
def find_word(grid, word):
    n = len(grid)
    vis = [[False] * n for _ in range(n)]
    directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]

    def dfs(cnt, x, y, path):
        if x < 0 or x >= n or y < 0 or y >= n or vis[x][y] or grid[x][y] != word[cnt]:
            return False
        if cnt == len(word) - 1:
            print(",".join(f"{i},{j}" for i, j in path))
            return True

        vis[x][y] = True
        for dx, dy in directions:
            a, b = x + dx, y + dy
            path.append((a, b))
            if dfs(cnt + 1, a, b, path):
                return True
            path.pop()
        vis[x][y] = False
        return False

    for i in range(n):
        for j in range(n):
            if grid[i][j] == word[0]:
                if dfs(0, i, j, [(i, j)]):
                    return
    print("N")

n = int(input())
grid = [input().split(',') for _ in range(n)]
word = input().strip()
find_word(grid, word)
  • Java
import java.util.*;

public class Main {
    static int n;
    static char[][] grid;
    static String word;
    static boolean[][] vis;
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, 1, -1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        sc.nextLine();
 

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

算法刷题笔记 文章被收录于专栏

本专栏收集并整理了一些刷题笔记

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务