Find if all the characters of a given word is present in a two dimensional matrix if the matrix can be traversed as described in the image below:
Java Program:
Java Program:
public class MatrixTraversalPrograms { public boolean driverForIsWordPresent(char[] in, char[][] matrix) { boolean wordFound = false; for(int i=0;i<matrix.length;i++) { for(int j=0;j<matrix[i].length;j++) { if(in[0] == matrix[i][j]) { wordFound = isWordPresent(in, matrix, i, j, 0); } if(wordFound) { break; } } if(wordFound) { break; } } return wordFound; } public boolean isWordPresent(char[] in, char[][] matrix, int i, int j, int index) { if(index == in.length - 1) { return true; } else { boolean complete = false; //Top Right if(i-1 >= 0 && j+1 < matrix[i].length && matrix[i-1][j+1] == in[index+1]) { complete = isWordPresent(in, matrix, i-1, j+1, index + 1); if(complete) { return true; } } //Right if(!complete && i >= 0 && i < matrix.length && j+1 < matrix[i].length && matrix[i][j+1] == in[index+1]) { complete = isWordPresent(in, matrix, i, j+1, index + 1); if(complete) { return true; } } //Bottom Right if(!complete && i+1 < matrix.length && j+1 < matrix[i+1].length && matrix[i+1][j+1] == in[index+1]) { complete = isWordPresent(in, matrix, i+1, j+1, index + 1); if(complete) { return true; } } //Bottom if(!complete && i+1 < matrix.length && j >= 0 && j < matrix[i+1].length && matrix[i+1][j] == in[index+1]) { complete = isWordPresent(in, matrix, i+1, j, index + 1); if(complete) { return true; } } //Bottom Left if(!complete && i+1 < matrix.length && j-1 >= 0 && matrix[i+1][j-1] == in[index+1]) { complete = isWordPresent(in, matrix, i+1, j-1, index + 1); if(complete) { return true; } } //Left if(!complete && i>=0 && i < matrix.length && j-1 >= 0 && matrix[i][j-1] == in[index+1]) { complete = isWordPresent(in, matrix, i, j-1, index + 1); if(complete) { return true; } } //Top Left if(!complete && i-1 >= 0 && j-1 >= 0 && matrix[i-1][j-1] == in[index+1]) { complete = isWordPresent(in, matrix, i-1, j-1, index + 1); if(complete) { return true; } } //Top if(!complete && i-1 >= 0 && j >= 0 && j < matrix[i-1].length && matrix[i-1][j] == in[index+1]) { complete = isWordPresent(in, matrix, i-1, j, index + 1); if(complete) { return true; } } return false; } } }
Unit Tests:
import static org.junit.Assert.*; import org.junit.Test; import junit.framework.Assert; public class MatrixTraversalTests { MatrixTraversalPrograms programInstance = new MatrixTraversalPrograms(); @Test public void testTwoCharacterPresent() { char[] in = {'a','b'}; char[][] matrix = new char[][]{ {'x','b'}, {'a','x'} }; Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix)); } @Test public void testTwoOnePresent() { char[] in = {'a','b'}; char[][] matrix = new char[][]{ {'x','c'}, {'a','x'} }; Assert.assertFalse(programInstance.driverForIsWordPresent(in, matrix)); } @Test public void testTwoBiggerMatrix() { char[] in = {'a','b'}; char[][] matrix = new char[][]{ {'x','x','x'}, {'x','b','x'}, {'a','x','x'} }; Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix)); } @Test public void testTwoRepeated() { char[] in = {'a','b'}; char[][] matrix = new char[][]{ {'x','x','x'}, {'x','b','x'}, {'a','b','x'} }; Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix)); } @Test public void testLarge() { char[] in = {'M','i','c','r','o','s','o','f','t'}; char[][] matrix = new char[][]{ {'x','x','x','x','x','x'}, {'x','r','o','x','x','x'}, {'x','x','c','s','x','x'}, {'x','x','i','o','f','x'}, {'x','M','x','x','f','x'}, {'x','x','x','t','x','x'} }; Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix)); } @Test public void testLargePartialPresent() { char[] in = {'M','i','c','r','o','s','o','f','t'}; char[][] matrix = new char[][]{ {'x','x','x','x','x','x'}, {'x','r','o','x','x','x'}, {'x','x','c','s','x','x'}, {'x','x','i','o','f','x'}, {'x','M','x','x','f','x'}, {'x','x','x','x','x','x'} }; Assert.assertFalse(programInstance.driverForIsWordPresent(in, matrix)); } @Test public void testOneCharacterPresent() { char[] in = {'a'}; char[][] matrix = new char[][]{ {'a'} }; Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix)); } @Test public void testOneCharacterAbsent() { char[] in = {'a'}; char[][] matrix = new char[][]{ {'b'} }; Assert.assertFalse(programInstance.driverForIsWordPresent(in, matrix)); } }