Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
949 views
in Online Assessments by Expert (111,330 points) | 949 views

1 Answer

0 like 0 dislike
Best answer

image

 

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);
  }
}

 

 

by Expert (111,330 points)

Get best answers to any doubt/query/question related to programming , jobs, gate, internships and tech-companies. Feel free to ask a question and you will receive the best advice/suggestion related to anything you ask about software-engineering , development and programming problems .