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;
}
}
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"));
}
}
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"));
}
}
This testcase finished after 0.015 seconds on my pc.
http://forum.javaeye.com/viewtopic.php?p=106316#106316
]]>
private String water = "
X";public int maxDistance(String water) {
this.water = water;
int max = 0;
int sum = 0;
for (int initial = 1; initial < water.length() + 1; initial++) {
sum = bounce(0, initial);
max = (sum > max ? sum : max);
}
return max;
}
private int bounce(int startDistance, int bounceDistance) {
if (bounceDistance == 0)
return startDistance;
if ((startDistance + bounceDistance) > water.length())
return -1;
if (water.charAt(startDistance + bounceDistance - 1) == 'X')
return startDistance;
return bounce(startDistance + bounceDistance, bounceDistance / 2);
}
public static void main(String[] args) {
SkipStones skipStones = new SkipStones();
System.out.println(skipStones.maxDistance(args[0]));
}
}
]]>