FrederichCheng
BAN USERThis solution doesn't trim all trailing spaces.
- FrederichCheng July 14, 2014Java:
public class Solution {
public static void main(String... args){
char[][] map = {{ 'S', 'N', 'B', 'S', 'N' },
{ 'B', 'A', 'K', 'E', 'A' },
{ 'B', 'K', 'B', 'B', 'K' },
{ 'S', 'E', 'B', 'S', 'E' }};
System.out.println(findPath(map, "SNAKES"));
}
public static int findPath(char[][] map, String target){
int count = 0;
for(int i = 0; i < map.length ; i++){
for(int j = 0; j < map[i].length; j++){
count += findPath(map, target, i, j, 0);
}
}
return count;
}
public static int findPath(char[][] map, String target, int startX, int startY, int targetIndex){
if(startX < 0 || startY < 0 || startX >= map.length || startY >= map[startX].length){
return 0;
}
char original = map[startX][startY];
if(original != target.charAt(targetIndex))
return 0;
if(targetIndex == target.length() - 1)
return 1;
int count = 0;
map[startX][startY] = '\0'; // avoid return back to visited node
count += findPath(map, target, startX+1, startY, targetIndex+1);
count += findPath(map, target, startX, startY+1, targetIndex+1);
count += findPath(map, target, startX-1, startY, targetIndex+1);
count += findPath(map, target, startX, startY-1, targetIndex+1);
map[startX][startY] = original;
return count;
}
}
To compute the time complexity, we can consider the searching path a DFS 4-way tree traversal with the depth equal to the length of searched string k - 1 (root's depth is 0), so searching each tree takes O(4^(k-1)) = O(2^2(k-1)) = O(2^2k). Since each node can be a root, there will be m*n (dimension of the map) trees to search. Therefore, the general time complexity is O(m*n*2^2k). Since 2^2k grows much faster than m*n, simply O(2^2k).
If there is no turning back, it would be a 3-way tree search except that the root has 4 child nodes, but this would have little impact on the time complexity (O(4*3^(k-2)) = O(2^2k)).
Try to use a Bit version Trie?
- FrederichCheng July 15, 2014Use a bit (namely, "time") to determine if a node represents a number, so you can use XOR ( time^=1 ) to determine if it appears odd times (if time == 1).
Traverse the trie, print those nodes with time == 1 (You also need to reconstruct the value of the node).
The time complexity is O(32*N) for 4-byte Integers = O(N), and the space complexity is bound by the maximum number of nodes in the trie (2^32). Although it seems large, it's O(1) by definition.