Find a String in a 2 dimensional Array

Question

This is a interview question which needs to be optimized for time.

Suppose you have a 2 dimensional Array and you have a String say "Amazon" inside the Array such that the individual characters can be present from Left to Right, Right to Left, Top to down and down to up.

I will explain with 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}
    };

The above Array has two Amazon Strings. You need to return the count of number of such strings present.

Answer 1

I have written a java code that solve this question

But it is expensive solution in terms of time complexity

as I traverse the 2d array scanning for 'A' then from that element I traverse in 4 directions scanning for M then A and so on

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

will be

O(N^2 * K^4) the 4 here is for the 4 directions that we have to search

here is the fully running 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;

}

}

Answer 2

Make a three-dimensional table where each position in the matrix refers to an array representing each letter in the alphabet. Perform two iterations at once from top, left to right and right to left, row by row: if the string exists, you will encounter either its first or last letter (the only way you can encounter a middle letter is if you've already seen the first or last part of its connected match). Aggregate your left-right findings, but table the position of the element below at the index representing the next possible character with the current length and direction. If a table match is encountered, convert it into a complete or another partial match (each such letter+position cell can hold more than one potential match).

Answer 3

I have done a simple bfs, every time the first character of the string toFind (in your case AMAZON) matches a 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 4

1. Iterate over matrix = O(N^2)
2. find the first occurrence of key[0] ie 'A' in Amazon and store it in [i,j]

3. start from matrix[i,j] and try to trace 'Amazon' using all four directions

   a. You can use BFS or DFS

   b. if found, increase count by 1

   c. if not found, continue

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

Answer 5

You gave only one example. If:

• All the 'filler' characters are always something not in the string
• The string is always complete and not split
• The string has at least one non repeating letter

Then you just need to count how many of those non repeating letters there are. For example, with 'AMAZON', you just need to count how many 'Z' (or 'M', or 'O', or 'N') are in the array.

That's not as general as a path finding algorithm but definitely faster.

Answer 6

You can run a BFS from each cell of the matrix having 'A' and count the number of way Amazon can be built. Finally add them all.

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