Find word in two dimensional char array

Question

Task: I have two dimensional array of chars filled with random values [a-z] and need to find if the word ala appears vertically, horizontally or diagonally in it.

In my program, I go through all characters and try to find word in all dimensions.

I feel there is more intelligent way to do this task which will:

Work with words of different length without hard-coding.
Replace bunch of if statements so it will be easier.

Any advice?

import java.util.Random;

public class Ala {
    public static void main(String[] args) {
        Random randomGenerator = new Random();
        char[][] arr = new char[50][50];
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                arr[i][j] = (char) (randomGenerator.nextInt(26)+97);
            }
        }
        for (int i = 0; i < arr.length; i++) {
                System.out.printf("%-3d", i);
        }
        System.out.println();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j]+"  ");
            }
            System.out.println();
        }
        boolean ala = false;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (j>1) {
                    if (arr[i][j] == 'a' && arr[i][j - 1] == 'l' && arr[i][j - 2] == 'a') {//left
                        ala = true;
                        System.out.println(i + " " + j);
                    } 
                }
                if (j<arr[i].length-2) {
                    if (arr[i][j] == 'a' && arr[i][j + 1] == 'l' && arr[i][j + 2] == 'a') {//rigth
                        ala = true;
                        System.out.println(i + " " + j);
                    } 
                }
                if (i<arr.length-2) {
                    if (arr[i][j] == 'a' && arr[i + 1][j] == 'l' && arr[i + 2][j] == 'a') {//bot
                        ala = true;
                        System.out.println(i + " " + j);
                    } 
                }
                if (i>1) {
                    if (arr[i][j] == 'a' && arr[i-1][j] == 'l' && arr[i - 2][j] == 'a') {//top
                        ala = true;
                        System.out.println(i + " " + j);
                    } 
                }
                if (i<arr.length-2 && j<arr[i].length-2) {
                    if (arr[i][j] == 'a' && arr[i + 1][j + 1] == 'l' && arr[i + 2][j + 2] == 'a') {//bot&rigth
                        ala = true;
                        System.out.println(i + " " + j);
                    } 
                }
                if (i>1 && j>1) {
                    if (arr[i][j] == 'a' && arr[i - 1][j - 1] == 'l' && arr[i - 2][j - 2] == 'a') {//top&left
                        ala = true;
                        System.out.println(i + " " + j);
                    } 
                }
                if (i>1 && j<arr[i].length-2) {
                    if (arr[i][j] == 'a' && arr[i - 1][j + 1] == 'l' && arr[i - 2][j + 2] == 'a') {//top&rigth
                        ala = true;
                        System.out.println(i + " " + j);
                    } 
                }
                if (i<arr.length-2 && j>1) {
                    if (arr[i][j] == 'a' && arr[i + 1][j - 1] == 'l' && arr[i + 2][j - 2] == 'a') {//bot&left
                        ala = true;
                        System.out.println(i + " " + j);
                    } 
                }
            }
        }
        System.out.println(ala);
    }
}

TheCoffeeCup · Accepted Answer · 2015-11-22 18:38:45Z

To expand on @Caridorc's answer:

The method suggested is indeed the fastest way to do this type of question. First, you create a method with a two-dimensional char array and a String to look for:

public static boolean contains(char[][] grid, String word) {

}

Then, you implement the pseudocode:

public static boolean contains(char[][] grid, String word) {
    return verticalContains(grid, word)
            || horizontalContains(grid, word)
            || diagonalContains(grid, word);
}

And the methods:

private static boolean verticalContains(char[][] grid, String word) {
    for (char[] row : grid) {
        if (new String(row).contains(word)) {
            return true;
        }
    }
    return false;
}

private static boolean horizontalContains(char[][] grid, String word) {
    int wordLength = word.length();
    int max = grid.length - wordLength;
    char[] wordArray = word.toCharArray();
    for (int i = 0, length = grid[0].length; i < length; i++) {
        loop: for (int j = 0; j < max; j++) {
            for (int k = j; k < wordArray.length; k++) {
                if (wordArray[k - j] != grid[k][i]) {
                    continue loop;
                }
            }
            return true;
        }
    }
}

Diagonal is a bit trickier:

private static boolean diagonalContains(char[][] grid, String word) {
    int wordLength = word.length();
    char[] wordArray = word.toCharArray();
    for (int i = 0, length = grid.length; i < length; i++) {
        loop: for (int j = 0, k = i, subLength = grid[i].length;
                j < subLength && k >= wordLength; j++, k--) {
            for (int l = 0; l < wordLength; l++) {
                if (grid[j + l][k - l] != wordArray[l]) {
                    continue loop;
                }
                return true;
            }
        }
    }
}

Notice that vertical checks are easier, due to the easy creation of a String with a char array. Horizontal and diagonal is similar in structure.

You can even make it OOP:

import java.util.Arrays;

public class CharGrid {

    private final char[][] grid;

    public CharGrid(char[][] grid) {
        int length = grid.length;
        this.grid = copyArray(grid);
    }

    public char[][] getGrid() {
        return copyArray(grid)
    }

    private char[][] copyArray(char[][] array) {
        char[][] result = Arrays.copy(array, length);
        for (int i = 0; i < length; i++) {
            result[i] = Arrays.copy(array[i], array[i].length);
        }
        return result;
    }

    public boolean contains(String word) {
        return verticalContains(grid, word)
                || horizontalContains(grid, word)
                || diagonalContains(grid, word);
    }

    private boolean verticalContains(String word) {
        for (char[] row : grid) {
            if (new String(row).contains(word)) {
                return true;
            }
        }
        return false;
    }

    private boolean horizontalContains(String word) {
        int wordLength = word.length();
        int max = grid.length - wordLength;
        char[] wordArray = word.toCharArray();
        for (int i = 0, length = grid[0].length; i < length; i++) {
            loop: for (int j = 0; j < max; j++) {
                for (int k = j; k < wordArray.length; k++) {
                    if (wordArray[k - j] != grid[k][i]) {
                        continue loop;
                    }
                }
                return true;
            }
        }
    }

    private boolean diagonalContains(String word) {
        int wordLength = word.length();
        char[] wordArray = word.toCharArray();
        for (int i = 0, length = grid.length; i < length; i++) {
            loop: for (int j = 0, k = i, subLength = grid[i].length;
                    j < subLength && k >= wordLength; j++, k--) {
                for (int l = 0; l < wordLength; l++) {
                    if (grid[j + l][k - l] != wordArray[l]) {
                        continue loop;
                    }
                    return true;
                }
            }
        }
    }

}

Caridorc · Accepted Answer · 2015-11-22 16:52:38Z

Your code is indeed sub-optimal.

When looking at a task do not start writing some loops, but think about it is made up of simpler tasks.

A word is in a two-dimensional crossword grid if any of the below is True:

The word is in any of the rows.
The word is in any of the columns.
The word is in any of the diagonals.

So, the general outline of the method may be:

class WordGrid {
  public contains(String word) {
    return any(word in row for row in getRows())                ||
           any(word in column for column in getColumns())       || 
           any(word in diagonal for diagonal in getDiagonals())
   }
}

Now you just have to translate this pseudocode to real code and implement the three get methods and the problem will be solved.

This is my suggestion because:

The general idea can be understood at a glance, if the reader wants more details he can read the helper methods.
It is made of many small pieces, that may be reused and are simpler to write on their own.
It is general working, for any grid and word size.

Anthony Fawcett · Accepted Answer · 2015-11-23 01:42:36Z

To expand on TheCoffeeCup's answer:

When scanning for matches, make sure to order your tests from least expensive to most expensive (or most trivial to least trivial). You only want to be performing the most expensive scan operations when you absolutely need to.

Depending on the persistence of your grid and the number of searches being performed, you may find it more efficient to pre-convert your 2-dimensional array of characters into a one dimensional array of strings (one string per row).

Expanding on that, searching vertically is essentially the same as searching horizontally except the characters are translated in position. If you create two single dimension arrays of strings - one for horizontal scanning, and one for vertical scanning- you can perform that part of the scanning using the same simple loop.

Sᴀᴍ Onᴇᴌᴀ · Accepted Answer · 2019-05-18 15:18:40Z

make String of each like vertical,horizontal,diagonal and use string method contains, :)

for(i=0;i<arr.length;i++) {
        for(j=0;j<arr.length;j++) {`enter code here`
            horizontal = horizontal+""+arr[i][j];
            vertical = vertical +""+arr[j][i];
            if(i==j)
                diagonal = diagonal+""+arr[i][j];
        }
        horizontal = horizontal +" ";
        vertical = vertical +" ";
    }
    System.out.println("horizontal String : "+horizontal);
    System.out.println(horizontal.contains(searchString));
    System.out.println("vertical String : "+vertical);
    System.out.println(vertical.contains(searchString));
    System.out.println("diagonal String : "+diagonal);
    System.out.println(diagonal.contains(searchString));

Stack Exchange Network

Find word in two dimensional char array

4 Answers 4

You must log in to answer this question.

Hot Network Questions

Find word in two dimensional char array

4 Answers 4

You must log in to answer this question.

Related

Hot Network Questions