Find a string in a two-dimensional array

Question

This is an interview question that needs to be optimized for time.

Suppose you have a two-dimensional array and you have the string "Amazon" inside the array, so that individual characters can be present from left to right, from right to left, from top to bottom and down.

I will explain an example:

char[][] a = { {B,B,A,B,B,N}, {B,B,M,B,B,O}, {B,B,A,B,B,Z}, {N,O,Z,B,B,A}, {B,B,B,B,B,M}, {B,B,B,B,B,A} }; 

In the array above there are two rows of Amazon. You need to return a counter for the number of such rows.

Answer 1

I made a simple bfs, every time the first character of the toFind string (in your case AMAZON) matches the character in the 2D array. A simple visited 2D array is used to check for marked characters in one iteration:

 public class FindStrings { private static int count = 0; // Final Count public static void find(Character[][] a, String toFind) { int rows = a.length; int col = a[0].length; boolean[][] visited = new boolean[a.length][a[0].length]; for (int i = 0; i < rows; i++) { for (int j = 0; j < col; j++) { if (a[i][j] == toFind.charAt(0)) { findUtil(visited, a, i, j, 0, toFind, new StringBuilder(), rows - 1, col - 1,new ArrayList<String>()); visited[i][j] = false; } } } } private static void findUtil(boolean[][] visited, Character[][] a, int i, int j, int index, String toFind, StringBuilder result, int R, int C,ArrayList<String> list) { result.append(a[i][j]); //This list just prints the entire Path list.add(i+"-"+j); if (index == toFind.length() - 1 && result.toString().equals(toFind)) { System.out.println(list.toString()); count++; return; } visited[i][j] = true; // Just to mark the character so that one character is not visited twice for a string match int nextIndex = index + 1; //Next index of the String to be compared int nextR, nextC; //Down if (i + 1 >= 0 && j >= 0 && i + 1 <= R && j <= C && !visited[i + 1][j] && a[i + 1][j] == toFind.charAt(nextIndex)) { nextR = i + 1; nextC = j; findUtil(visited, a, nextR, nextC, nextIndex, toFind, new StringBuilder(result), R, C,new ArrayList<>(list)); //Every time we are done with the next character in the 2D Array we mark it visited visited[nextR][nextC] = false; } //Right if (i >= 0 && j + 1 >= 0 && i <= R && j + 1 <= C && !visited[i][j + 1] && a[i][j + 1] == toFind.charAt(nextIndex)) { nextR = i; nextC = j + 1; findUtil(visited, a, nextR, nextC, nextIndex, toFind, new StringBuilder(result), R, C,new ArrayList<>(list)); visited[nextR][nextC] = false; } //Left if (i >= 0 && j - 1 >= 0 && i <= R && j - 1 <= C && !visited[i][j - 1] && a[i][j - 1] == toFind.charAt(nextIndex)) { nextR = i; nextC = j - 1; findUtil(visited, a, nextR, nextC, nextIndex, toFind, new StringBuilder(result), R, C,new ArrayList<>(list)); visited[nextR][nextC] = false; } //Up if (i - 1 >= 0 && j >= 0 && i - 1 <= R && j <= C && !visited[i - 1][j] && a[i - 1][j] == toFind.charAt(nextIndex)) { nextR = i - 1; nextC = j; findUtil(visited, a, nextR, nextC, nextIndex, toFind, new StringBuilder(result), R, C,new ArrayList<>(list)); visited[nextR][nextC] = false; } } public static int getCount() { return count; } public static void main(String[] args) { Character[][] a = new Character[][]{ {'B', 'B', 'A', 'B', 'B', 'N'}, {'B', 'B', 'M', 'B', 'B', 'O'}, {'B', 'B', 'A', 'B', 'B', 'Z'}, {'B', 'O', 'Z', 'O', 'N', 'A'}, {'B', 'B', 'O', 'Z', 'B', 'M'}, {'B', 'B', 'N', 'A', 'M', 'A'} }; String toFind = "AMAZON"; find(a, toFind); System.out.println(getCount()); } 

Answer 2

You can run BFS from each cell in the matrix that has an “A” and count the number of ways to create Amazon. Finally add them all.

Edges: Adjacent (up, down, left, right) node (cell) have a directed edge from the current node (cell) if it contains the next Amazon character. Just an example, all adjacent nodes having 'N' have a directed edge from node having 'O'.

Answer 3

You gave only one example. If a:

• All the characters "filler" always have something out of line
• The line is always complete and not split
• A string contains at least one non-repeating letter

Then you just need to calculate how many of them are not repeated. For example, using "AMAZON" you just need to calculate how many "Z" (or "M", or "O" or "N") are in the array.

This is not as common as the pathfinding algorithm, but definitely faster.

Answer 4

• We pass to the matrix = O (N ^ 2)
• find the first occurrence of key [0], that is, “A” in Amazon, and save it in [i, j]

• start with the matrix [i, j] and try to trace Amazon using all four directions

  but. You can use BFS or DFS

  b. if found, increase the quantity by 1

  from. if not found, continue

Time complexity = O (N ^ 2 + N) {using DFS}

Answer 5

Make a three-dimensional table where each position in the matrix refers to an array representing each letter in the alphabet. Perform two iterations immediately from above, from left to right and from right to left, line by line: if a line exists, you will encounter its first or last letter (the only way to meet the middle letter is if you have already seen the first or last part of the match associated with it). The totality of your left results, but write down the position of the element below in the index representing the next possible character with the current length and direction. If a column occurs, convert it to a full or another partial match (each cell with such a + cell may contain more than one potential match).

Answer 6

I wrote Java code that solves this issue

But this is an expensive solution in terms of time complexity

when I cross scan a 2d array for "A", then from this element I cross scan in 4 directions for M, then A, etc.

So, the worst case scenario, if we assume that 1 scan of the array is n ^ 2 and the length of the scanned word is K

will be

O (N ^ 2 * K ^ 4) here are 4 for the four directions we should look for

here is a fully run class

 public class Treetest { public static void main(String[] args) { char[][] a = { {'B', 'B', 'A', 'B', 'B', 'N'}, {'B', 'B', 'M', 'B', 'B', 'O'}, {'B', 'B', 'A', 'B', 'B', 'Z'}, {'N', 'O', 'Z', 'A', 'M', 'A'}, //{'N', 'O', 'Z', 'B', 'B', 'A'}, {'B', 'B', 'B', 'B', 'B', 'M'}, {'B', 'B', 'B', 'B', 'B', 'A'} }; int vertical = 0; int horiz = 0; int solutioncount = 0; for (char[] horizantal : a) { for (char element : horizantal) { if (element == 'A') { if (findnextChar(horiz, vertical, "A", a)) solutioncount++; } horiz++; } horiz = 0; vertical++; } System.out.println("Solution Count is : " + solutioncount); } public static boolean findnextChar(int posx, int posy, String currentFind, char[][] a) { char nextchar = 0; boolean checkMatch = false; switch (currentFind) { case "A": nextchar = 'M'; break; case "AM": nextchar = 'A'; break; case "AMA": nextchar = 'Z'; break; case "AMAZ": nextchar = 'O'; break; case "AMAZO": nextchar = 'N'; checkMatch = true; break; } String nextString = currentFind + String.valueOf(nextchar); if (posx - 1 >= 0 && a[posy][posx - 1] == nextchar) { if (checkMatch) { return true; } return findnextChar(posx - 1, posy, nextString, a); } if (posx + 1 <= a[0].length - 1 && a[posy][posx + 1] == nextchar) { if (checkMatch) { return true; } return findnextChar(posx + 1, posy, nextString, a); } if (posy - 1 >= 0 && a[posy - 1][posx] == nextchar) { if (checkMatch) { return true; } return findnextChar(posx, posy - 1, nextString, a); } if (posy + 1 <= a[0].length - 1 && a[posy + 1][posx] == nextchar) { if (checkMatch) { return true; } return findnextChar(posx, posy + 1, nextString, a); } return false; } 

}