Overview

I was playing this word search game with my children when I realized that I can create a simple Java application that search for words in a grid. I uploaded the source at https://github.com/johnpili/search-a-word-in-a-two-dimensional-array-using-java

MainApp.java

In this example, I created a 15×15 character array and populate it with strings per row.

public class MainApp {
    public static void main(String[] args) {
        char[][] m = new char[15][15];
        m[0] = "LRHCODRUMAJTMLE".toCharArray();
        m[1] = "IYDTANDARPMAKLJ".toCharArray();
        m[2] = "SNOTKKASHINGLHD".toCharArray();
        m[3] = "IARESWALTONIKAJ".toCharArray();
        m[4] = "NMTFAQLHBTSOKLM".toCharArray();
        m[5] = "TDEFPMCPYOWHGUA".toCharArray();
        m[6] = "TIGUIEIANKMUYAB".toCharArray();
        m[7] = "ARABRAGTDELWLDR".toCharArray();
        m[8] = "RFJBEMPXTENTKDA".toCharArray();
        m[9] = "NRLPDBDOHALXNAM".toCharArray();
        m[10] = "AAQRZAVUTHLSWWO".toCharArray();
        m[11] = "UFRZQNRMAAGDOBV".toCharArray();
        m[12] = "LKJKNIRBDSNNJNI".toCharArray();
        m[13] = "TCEGATESCMLIIMC".toCharArray();
        m[14] = "FEMORDASHOVANSH".toCharArray();
        ConsoleDisplay consoleDisplay = new ConsoleDisplay(m);
        try {
            if (args.length > 0) {
                SearchResult result = WordSearch.searchWord(m, args[0].toUpperCase());
                if (result != null) {
                    consoleDisplay.displayResult(result);
                }
                return;
            }
            consoleDisplay.displayGrid();
        } catch (Exception exception) {
            System.out.println(exception.getMessage());
        }
    }
}

WordSearch.java

I started this simple search algorithm by creating a character index of each letter (a lookup table). This way, I have the positions of each letter occurrences with xs and ys. Using this character map, I check the first letter of the search keyword and iterate only to those locations with the matching letter. I used an angle-based directional string extraction to retrieve the word from the grid and check if it matches against the search keyword.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class WordSearch {
    private static Map<Character, List<Point>> generateCharacterMap(char[][] m) {
        Map<Character, List<Point>> cm = new HashMap<>();
        for (int y = 0; y < m[0].length; ++y) {
            for (int x = 0; x < m.length; ++x) {
                List<Point> tmp;
                if (!cm.containsKey(m[y][x])) {
                    tmp = new ArrayList<>();
                } else {
                    tmp = cm.get(m[y][x]);
                }
                tmp.add(new Point(x, y));
                cm.put(m[y][x], tmp);
            }
        }
        return cm;
    }

    public static SearchResult search(char[][] matrix, String keyword) throws Exception {
        Map<Character, List<Point>> characterMap = generateCharacterMap(matrix);
        if (keyword != null) {
            int keySize = keyword.length();
            if (keySize == 0) {
                throw new Exception("Keyword is empty");
            }

            if (characterMap.containsKey(keyword.charAt(0))) {
                for (Point point : characterMap.get(keyword.charAt(0))) {
                    for (int a = 0; a <= 315; a += 45) {
                        SearchResult searchResult = extractByDirection(matrix, point, keySize, a);
                        if (searchResult != null && searchResult.getKeyword().equals(keyword)) {
                            return searchResult;
                        }
                    }
                }
            }
            return null;
        }
        throw new NullPointerException("Matrix is null");
    }

    private static SearchResult extractByDirection(char[][] m, Point p, int size, int d) {
        StringBuilder sb = new StringBuilder();
        Point[] c = new Point[size];
        if (d == Angle.A0) {
            if ((p.getX() + size) <= m.length) {
                for (int x = p.getX(), i = 0; x < (p.getX() + size); ++x, ++i) {
                    sb.append(m[p.getY()][x]);
                    c[i] = new Point(x, p.getY());
                }
                return new SearchResult(p, new Point(p.getX() + size, p.getY()), sb.toString(), c);
            }
        } else if (d == Angle.A45) {
            if (((p.getY() - size) >= 0) && ((p.getX() + size <= m.length))) {
                for (int y = p.getY(), x = p.getX(), i = 0; (y > (p.getY() - size)) && (x < (p.getX() + size)); --y, ++x, ++i) {
                    sb.append(m[y][x]);
                    c[i] = new Point(x, y);
                }
                return new SearchResult(p, new Point((p.getX() + size), (p.getY() - size)), sb.toString(), c);
            }
        } else if (d == Angle.A90) {
            if ((p.getY() - size) >= 0) {
                for (int y = p.getY(), i = 0; y > (p.getY() - size); --y, ++i) {
                    sb.append(m[y][p.getX()]);
                    c[i] = new Point(p.getX(), y);
                }
                return new SearchResult(p, new Point(p.getX(), (p.getY() - size)), sb.toString(), c);
            }
        } else if (d == Angle.A135) {
            if (((p.getY() - size) >= 0) && ((p.getX() - size >= 0))) {
                for (int y = p.getY(), x = p.getX(), i = 0; (y > (p.getY() - size)) && (x > (p.getX() - size)); --y, --x, ++i) {
                    sb.append(m[y][x]);
                    c[i] = new Point(x, y);
                }
                return new SearchResult(p, new Point((p.getX() - size), (p.getY() - size)), sb.toString(), c);
            }
        } else if (d == Angle.A180) {
            if ((p.getX() - size) >= 0) {
                for (int x = p.getX(), i = 0; x > (p.getX() - size); --x, ++i) {
                    sb.append(m[p.getY()][x]);
                    c[i] = new Point(x, p.getY());
                }
                return new SearchResult(p, new Point((p.getX() - size), p.getY()), sb.toString(), c);
            }
        } else if (d == Angle.A225) {
            if (((p.getY() + size) <= m[0].length) && ((p.getX() - size >= 0))) {
                for (int y = p.getY(), x = p.getX(), i = 0; (y < (p.getY() + size)) && (x > (p.getX() - size)); ++y, --x, ++i) {
                    sb.append(m[y][x]);
                    c[i] = new Point(x, y);
                }
                return new SearchResult(p, new Point((p.getX() + size), (p.getY() + size)), sb.toString(), c);
            }
        } else if (d == Angle.A270) {
            if ((p.getY() + size) <= m[0].length) {
                for (int y = p.getY(), i = 0; y < (p.getY() + size); ++y, ++i) {
                    sb.append(m[y][p.getX()]);
                    c[i] = new Point(p.getX(), y);
                }
                return new SearchResult(p, new Point(p.getX(), (p.getY() + size)), sb.toString(), c);
            }
        } else if (d == Angle.A315) {
            if (((p.getY() + size) <= m[0].length) && ((p.getX() + size <= m.length))) {
                for (int y = p.getY(), x = p.getX(), i = 0; (y < (p.getY() + size)) && (x < (p.getX() + size)); ++y, ++x, ++i) {
                    sb.append(m[y][x]);
                    c[i] = new Point(x, y);
                }
                return new SearchResult(p, new Point((p.getX() + size), (p.getY() + size)), sb.toString(), c);
            }
        }
        return null;
    }

    private class Angle {
        public static final int A0 = 0;
        public static final int A45 = 45;
        public static final int A90 = 90;
        public static final int A135 = 135;
        public static final int A180 = 180;
        public static final int A225 = 225;
        public static final int A270 = 270;
        public static final int A315 = 315;
    }
}

Demo/Screenshots

Search for GATES

Search for GATES

Search for ELLISON

Search for ELLISON

Search for ALBRECHT

Search for ALBRECHT