string - 在网格中查找一系列字符以形成字符串（一次向下或向右移动一步）

首先让我们在要使用的图形结构中定义一个节点。为了我们的目的，一个节点需要跟踪它的位置和它所代表的字符。

static class Node{

    int x;
    int y;
    char c;
    List<Node> adjecent = new ArrayList<>();

    public Node(int x, int y, char c){
        this.x = x;
        this.y = y;
        this.c = c;
    }

}

然后我们需要一种简单的方法来构建节点网格，代表我们的字符网格。我选择实现这一点，以便单个字符串对象可以代表整个网格，并且可以从该字符串构建网格。

public static Node[][] buildGraph(String s){
    String[] lns = s.split("\n");
    int M = lns.length;
    int N = lns[0].length();
    Node[][] out = new Node[M][N];
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            out[i][j] = new Node(i,j,lns[i].charAt(j));
            if(i != 0)
                out[i-1][j].adjecent.add(out[i][j]);
            if(j != 0)
                out[i][j-1].adjecent.add(out[i][j]);
        }
    }
    return out;
}

现在是实际的算法。哪个（正如评论所建议的）基于 BFS。递归的入口点是以下方法，它检查网格中可能作为有效起始位置的所有节点。

private static void buildWord(Node[][] mtx, String target){
    char c = target.charAt(0);
    for(int i=0;i<mtx.length;i++){
        for(int j=0;j<mtx.length;j++){
            if(mtx[i][j].c == c){
                List<Node> tmp = new ArrayList<>();
                tmp.add(mtx[i][j]);
                buildWord(mtx[i][j], target, tmp);
            }
        }
    }
}

对于每个有效的起始位置，它调用方法“buildWord”，该方法试图找到拼写目标单词的路径的其余部分。这是一个相对简单的 BFS。

private static void buildWord(Node start, String target, List<Node> path){
    if(path.size() > target.length()){
        return;
    } else if(path.size() == target.length()){
        String tmp = "";
        for(Node n : path)
            tmp += n.c;
        if(tmp.equals(target)){
            for(int i=0;i<path.size();i++)
                System.out.print("[" + path.get(i).x + ", " + path.get(i).y + "](" + path.get(i).c + ") --> ");
            System.out.print("\n");
        }
    } else {
        char nxtChar = target.charAt(path.size());
        for(Node n : start.adjecent){
            if(n.c == nxtChar){
                path.add(n);
                buildWord(n, target, path);
                path.remove(path.size() - 1);
            }
        }
    }
}

main 方法从字符串构建图，然后尝试查找路径。正在构建的图表代表

abc
def
ghi

算法试图找到“adeh”这个词

public static void main(String[] args){
    Node[][] matrix = buildGraph("abc\ndef\nghi");
    buildWord(matrix, "adeh");
}

它找到路径并打印它

[0, 0](a) --> [1, 0](d) --> [1, 1](e) --> [2, 1](h) -->

string - 在网格中查找一系列字符以形成字符串（一次向下或向右移动一步）

问题描述

解决方案

推荐阅读