public class WordPath {
public int countPaths(String[] grid, String find) {
int length = grid.length + 2;
//convert "grid" from String to char matrix
char[][] charGrid = new char[length][length];
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
if (i == 0 || i == length - 1 || j == 0 || j == length - 1)
charGrid[i][j] = '0';
else
charGrid[i][j] = grid[i - 1].charAt(j - 1);
}
}
//convert "find" from String to char array
char[] charFind = new char[find.length()];
for (int k = 0; k < find.length(); k++)
charFind[k] = find.charAt(k);
//use three dimensions "degree" to hold the in-degree of the vertex of graph
int[][][] degree = new int[length][length][find.length()];
// k=0
for (int i = 0; i < length; i++)
for (int j = 0; j < length; j++) {
degree[i][j][0] = ((charGrid[i][j] == charFind[0]) ? 1 : 0);
}
// fill the degree
for (int k = 1; k < find.length(); k++) {
for (int i = 0; i < length; i++)
for (int j = 0; j < length; j++) {
if (charGrid[i][j] != charFind[k])
degree[i][j][k] = 0;
else {
degree[i][j][k] = degree[i - 1][j - 1][k - 1] + degree[i - 1][j][k - 1]
+ degree[i - 1][j + 1][k - 1] + degree[i + 1][j - 1][k - 1]
+ degree[i + 1][j][k - 1] + degree[i + 1][j + 1][k - 1]
+ degree[i][j - 1][k - 1] + degree[i][j + 1][k - 1];
}
}
}
//calculate the sum
int sum = 0;
for (int i = 0; i < length; i++)
for (int j = 0; j < length; j++) {
sum += degree[i][j][find.length() - 1];
if (sum > 1000000000) {
return -1;
}
}
return sum;
}
}
- TestCase
public class WordPathTest extends TestCase {
public void testCountPaths() {
WordPath wordPath = new WordPath();
assertEquals(2, wordPath.countPaths(new String[] { "ABC", "FED", "GAI" }, "ABCDEA"));
assertEquals(0, wordPath.countPaths(new String[] { "ABC", "DEF", "GHI" }, "ABCD"));
assertEquals(108, wordPath.countPaths(new String[] { "AA", "AA" }, "AAAA"));
assertEquals(56448, wordPath.countPaths(new String[] { "ABABA", "BABAB", "ABABA", "BABAB", "ABABA" },
"ABABABBA"));
assertEquals(-1, wordPath.countPaths(new String[] { "AAAAA", "AAAAA", "AAAAA", "AAAAA", "AAAAA" },
"AAAAAAAAAAA"));
assertEquals(0, wordPath.countPaths(new String[] { "AB", "CD" }, "AA"));
}
}