【算法题】找单词

共计 1892 个字符，预计需要花费 5 分钟才能阅读完成。

题目描述

给一个字符串和一个二维字符数组，如果该字符串存在于该数组中，则按字符串的字符顺序输出字符串每个字符所在单元格的位置下标字符串，如果找不到返回字符串”N”。

1. 需要按照字符串的字符组成顺序搜索，且搜索到的位置必须是相邻单元格，其中“相邻单元格”是指那些水平相邻或垂直相邻的单元格。
2. 同一个单元格内的字母不允许被重复使用。
3. 假定在数组中最多只存在一个可能的匹配。

题目要求

• 输入描述:
  

  1. 第1行为一个数字（N）指示二维数组在后续输入所占的行数。
  2. 第2行到第N+1行输入为一个二维大写字符数组，每行字符用半角,分割。
  3. 第N+2行为待查找的字符串，由大写字符组成。
  4. 二维数组的大小为N*N，0<N<=100。
  5. 单词长度K，0<K<1000。

• 输出描述:
  

  输出一个位置下标字符串，拼接格式为：第1个字符行下标+”,”+第1个字符列下标+”,”+第2个字符行下标+”,”+第2个字符列下标…+”,”+第N个字符行下标+”,”+第N个字符列下标

示例1

输入

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分别对应二维数组的[0,0] [0,1] [0,2] [1,2] [2,2] [2,3]下标位置

JAVA解法

import java.util.Scanner;

/**
 * @since 2022年4月23日
 */
public class FindWord {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = Integer.parseInt(scanner.nextLine());
        char[][] twodim = new char[N][N];
        int count = 0;
        while (count < N) {
            String line = scanner.nextLine();
            String replacedLine = line.replace(",", "");
            for (int i = 0; i < N; i++) {
                twodim[count][i] = replacedLine.charAt(i);
            }
            count++;
        }
        String lastLine = scanner.nextLine();

        StringBuilder str = new StringBuilder();
        boolean result = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (lastLine.charAt(0) == twodim[i][j]) {
                    StringBuilder resultStr = new StringBuilder();
                    if (find(twodim, lastLine, i, j, 0, resultStr)) {
                        str = resultStr;
                    }
                }
            }
        }

        System.out.println(str.reverse());

    }

    private static boolean find(char[][] twodim, String lastLine, int i, int j, int indexOfStr, StringBuilder resultStr) {
        if (indexOfStr >= lastLine.length()) {
            return true;
        }
        if (i < 0 || i >= twodim.length || j < 0 || j >= twodim.length || twodim[i][j] != lastLine.charAt(indexOfStr)) {
            return false;
        }
        twodim[i][j] += 300; // 防止该位置被重复判断

        boolean result =
                find(twodim, lastLine, i - 1, j, indexOfStr + 1, resultStr)
                        || find(twodim, lastLine, i + 1, j, indexOfStr + 1, resultStr)
                        || find(twodim, lastLine, i, j - 1, indexOfStr + 1, resultStr)
                        || find(twodim, lastLine, i, j + 1, indexOfStr + 1, resultStr);
        twodim[i][j] -= 300;
        if (result) {
            if (indexOfStr == 0) {
                resultStr.append(j).append(",").append(i);
            }
            if (indexOfStr != 0) {
                resultStr.append(j).append(",").append(i).append(",");
            }
        }
        return result;
    }
}