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 ELLISON
Search for ALBRECHT