My Solution
public class Solution {
// If you need extra classes, you can define them privately here within class Solutionc
static class Pair{
int x, y;
public Pair(int x, int y){
this.x = x;
this.y = y;
}
public String toString(){
return x+" " + y;
}
}
static void findWord(String word, String[][] grid) {
for(int i=0;i<grid.length;i++){
for(int j =0;j<grid[0].length;j++){
findWordRecur(grid, i, j, 0, word, new ArrayList<>());
if(answer.size()!=0){
for(int k=0;k<answer.size()/2;k++){
System.out.println(answer.get(k));
}
return;
}
}
}
System.out.println("None");
}
static List<Pair> answer = new ArrayList<>();
static void findWordRecur(String [][] grid, int x, int y, int pointer, String word, List<Pair> path){
if(pointer==word.length()){
answer.addAll(path);
return;
}
if(x < 0 || x>= grid.length || y<0 || y >= grid[0].length){
return;
}
if(grid[x][y].equals(""+word.charAt(pointer))){
path.add(new Pair(x,y));
findWordRecur(grid, x+1, y, pointer+1, word, path);
findWordRecur(grid, x, y+1, pointer+1, word, path);
path.remove(path.size()-1);
}
}
// DO NOT MODIFY MAIN()
public static void main(String[] args) {
String arg0 = null;
List<String[]> arg1 = new ArrayList<String[]>();
String line;
boolean first_arg = true;
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
while ((line = br.readLine()) != null) {
if (line.equals("")) {
continue;
}
if(first_arg) {
arg0 = line;
first_arg = false;
} else {
arg1.add(line.split(" "));
}
}
} catch (IOException e) {
e.printStackTrace();
return;
}
String[][] grid = arg1.toArray(new String[arg1.size()][]);
findWord(arg0, grid);
}
}