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.
You can checkout the source code at https://github.com/johnpili/search-a-word-in-a-two-dimensional-array-using-java
Algorithm Concept
Project Structure
MainApp.java
In this example, I created a 15×15 character array and populate it with strings per row. This program uses the program argument to set the keyword.
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();
MatrixReader matrixReader = new MatrixReader(m);
ConsoleDisplay consoleDisplay = new ConsoleDisplay(m);
try {
if(args.length > 0)
{
SearchResult searchResult = matrixReader.searchWord(args[0]);
if(searchResult != null)
{
consoleDisplay.displayResult(searchResult);
}
}
}
catch(Exception exception)
{
System.out.println(exception.getMessage());
}
}
}
SearchResult.java
This class will contain the details of the found keyword. pointer1 will hold the first character position while pointer2 will hold the position the last character.
To help with console highlight, I added a pointer chains which will hold the sequence of position to highlight.
public class SearchResult {
private Pointer pointer1;
private Pointer pointer2;
private String keyword;
private Pointer[] chains;
public SearchResult(Pointer pointer1, Pointer pointer2, String keyword, Pointer[] chains)
{
this.pointer1 = pointer1;
this.pointer2 = pointer2;
this.keyword = keyword;
this.chains = chains;
}
public Pointer getPointer1()
{
return this.pointer1;
}
public Pointer getPointer2()
{
return this.pointer2;
}
public String getKeyword()
{
return this.keyword;
}
public Pointer[] getChains()
{
return this.chains;
}
}
MatrixReader.java
The search algorithm starts by iterating through the cells and check if the cell contains the starting character of the keyword.
It then performs a directional string extraction base on the keyword size and execute a string comparison. If the keyword is
found it returns the result.
The method extractByDirection has a logic to not execute the extraction if the starting position and angle of extraction will intersect with the array boundary.
public class MatrixReader implements IMatrixReader {
protected char[][] matrix;
protected int xmin = 0;
protected int ymin = 0;
protected int xmax = 0;
protected int ymax = 0;
public MatrixReader(char[][] matrix) {
this.matrix = matrix;
this.xmax = this.matrix[0].length;
this.ymax = this.matrix.length;
}
public SearchResult searchWord(String keyword) throws Exception {
if(this.matrix != null && keyword != null) {
int keySize = keyword.length();
if(keySize == 0)
{
throw new Exception("Keyword is empty");
}
for(int y = this.ymin; y < this.ymax; ++y){
for(int x = this.xmin; x < this.xmax; ++x)
{
if(this.matrix[y][x] == keyword.charAt(0))
{
SearchResult searchResult = extractByDirection(new Pointer(x, y), keySize, Angle.A0);
if(searchResult != null && searchResult.getKeyword().equals(keyword)) {
return searchResult;
}
searchResult = extractByDirection(new Pointer(x, y), keySize, Angle.A90);
if(searchResult != null && searchResult.getKeyword().equals(keyword)) {
return searchResult;
}
searchResult = extractByDirection(new Pointer(x, y), keySize, Angle.A180);
if(searchResult != null && searchResult.getKeyword().equals(keyword)) {
return searchResult;
}
searchResult = extractByDirection(new Pointer(x, y), keySize, Angle.A270);
if(searchResult != null && searchResult.getKeyword().equals(keyword)) {
return searchResult;
}
searchResult = extractByDirection(new Pointer(x, y), keySize, Angle.A45);
if(searchResult != null && searchResult.getKeyword().equals(keyword)) {
return searchResult;
}
searchResult = extractByDirection(new Pointer(x, y), keySize, Angle.A135);
if(searchResult != null && searchResult.getKeyword().equals(keyword)) {
return searchResult;
}
searchResult = extractByDirection(new Pointer(x, y), keySize, Angle.A225);
if(searchResult != null && searchResult.getKeyword().equals(keyword)) {
return searchResult;
}
searchResult = extractByDirection(new Pointer(x, y), keySize, Angle.A315);
if(searchResult != null && searchResult.getKeyword().equals(keyword)) {
return searchResult;
}
}
}
}
return null;
}
throw new NullPointerException("Matrix is null");
}
public SearchResult extractByDirection(Pointer pointer, int size, int direction) {
String sample = "";
Pointer[] chains = new Pointer[size];
if(direction == Angle.A0)
{
if((pointer.getX()+size) <= this.xmax)
{
for(int x = pointer.getX(), i = 0; x < (pointer.getX()+size); ++x, ++i)
{
sample += matrix[pointer.getY()][x];
chains[i] = new Pointer(x, pointer.getY());
}
return new SearchResult(pointer, new Pointer(pointer.getX()+size, pointer.getY()), sample, chains);
}
}
else if(direction == Angle.A90)
{
if((pointer.getY()-size) >= this.ymin)
{
for(int y = pointer.getY(), i = 0; y > (pointer.getY()-size); --y, ++i)
{
sample += matrix[y][pointer.getX()];
chains[i] = new Pointer(pointer.getX(), y);
}
return new SearchResult(pointer, new Pointer(pointer.getX(), (pointer.getY()-size)), sample, chains);
}
}
else if(direction == Angle.A180)
{
if((pointer.getX()-size) >= this.xmin)
{
for(int x = pointer.getX(), i = 0; x > (pointer.getX()-size); --x, ++i)
{
sample += matrix[pointer.getY()][x];
chains[i] = new Pointer(x, pointer.getY());
}
return new SearchResult(pointer, new Pointer((pointer.getX()-size), pointer.getY()), sample, chains);
}
}
else if(direction == Angle.A270)
{
if((pointer.getY()+size) <= this.ymax)
{
for(int y = pointer.getY(), i = 0; y < (pointer.getY()+size); ++y, ++i)
{
sample += matrix[y][pointer.getX()];
chains[i] = new Pointer(pointer.getX(), y);
}
return new SearchResult(pointer, new Pointer(pointer.getX(),(pointer.getY()+size)), sample, chains);
}
}
else if(direction == Angle.A45)
{
if(((pointer.getY()-size) >= this.ymin) && ((pointer.getX()+size <= this.xmax)))
{
for(int y = pointer.getY(), x = pointer.getX(), i = 0; (y > (pointer.getY()-size)) && (x < (pointer.getX()+size)); --y, ++x, ++i)
{
sample += matrix[y][x];
chains[i] = new Pointer(x, y);
}
return new SearchResult(pointer, new Pointer((pointer.getX()+size),(pointer.getY()-size)), sample, chains);
}
}
else if(direction == Angle.A135)
{
if(((pointer.getY()-size) >= this.ymin) && ((pointer.getX()-size >= this.xmin)))
{
for(int y = pointer.getY(), x = pointer.getX(), i = 0; (y > (pointer.getY()-size)) && (x > (pointer.getX()-size)); --y, --x, ++i)
{
sample += matrix[y][x];
chains[i] = new Pointer(x, y);
}
return new SearchResult(pointer, new Pointer((pointer.getX()-size),(pointer.getY()-size)), sample, chains);
}
}
else if(direction == Angle.A225)
{
if(((pointer.getY()+size) <= this.ymax) && ((pointer.getX()-size >= this.xmin)))
{
for(int y = pointer.getY(), x = pointer.getX(), i = 0; (y < (pointer.getY()+size)) && (x > (pointer.getX()-size)); ++y, --x, ++i)
{
sample += matrix[y][x];
chains[i] = new Pointer(x, y);
}
return new SearchResult(pointer, new Pointer((pointer.getX()+size),(pointer.getY()+size)), sample, chains);
}
}
else if(direction == Angle.A315)
{
if(((pointer.getY()+size) <= this.ymax) && ((pointer.getX()+size <= this.xmax)))
{
for(int y = pointer.getY(), x = pointer.getX(), i = 0; (y < (pointer.getY()+size)) && (x < (pointer.getX()+size)); ++y, ++x, ++i)
{
sample += matrix[y][x];
chains[i] = new Pointer(x, y);
}
return new SearchResult(pointer, new Pointer((pointer.getX()+size),(pointer.getY()+size)), sample, chains);
}
}
return null;
}
}
Demo/Screenshots
Conclusion
There are other algorithms and ways out there to solve this type of problem but in my situation and time constraint this is good enough.
