Сначала давайте определим узел в графовой структуре, которую мы будем использовать.Для наших целей узел должен отслеживать свою позицию и символ, который он представляет.
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;
}
}
Тогда нам нужен простой способ построения сетки узлов, представляющих нашу сетку символов.Я решил реализовать это так, чтобы один объект String мог представлять всю сетку, и сетка может быть построена из этой строки.
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);
}
}
}
}
Основной метод строит граф из String, а затем пытается найти путь.Построенный график представляет собой
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) -->