e******i
发帖数: 106 | 1 这是在career cup 上看到的题：
Given a hashmap M which is a mapping of characters to arrays of substitute
characters, and an input string S, return an array of all possible mutations
of S (where any character in S can be substituted with one of its
substitutes in M, if it exists).
What is the time complexity? What is the space complexity? Can you optimize
either?
Example input:
M = { f: [F, 4], b: [B, 8] }
S = fab
Expected output:
[fab, Fab, 4ab, faB, FaB, 4aB, fa8, Fa8, 4a8]
这是我的解法，用backtracking.
public static ArrayList getMutation(String str, HashMap
char[]> map){
ArrayList result = new ArrayList();
int lens = str.length();
if(lens == 0){
return result;
}
if(map.isEmpty()){
result.add(str);
return result;
}
char[] mutation = new char[lens];
getMutation(str, map, result, mutation, 0);
return result;
}
public static void getMutation(String str, HashMap
map, ArrayList result, char[] mutation, int index){
if(index == str.length()){
String newItem = new String(mutation);
result.add(newItem);
return;
}
char current = str.charAt(index);
if(map.containsKey(current)){
char[] choice = map.get(current);
for(int i = 0; i <= choice.length;i++){
if(i == 0){
mutation[index] = current;
getMutation(str, map,result, mutation, index+1);
}
else{
mutation[index] = choice[i-1];
getMutation(str, map, result, mutation, index+1);
}
}
}
else{
mutation[index] = current;
getMutation(str, map, result, mutation, index+1);
}
}
这道题很类似leetcode上电话号码那题。我想空间复杂度应该是O(n),可是时间复杂度
我有点confuse。 求大神指点，这样的backtracking时间复杂度该怎么算 | e******i
发帖数: 106 | 2 另外我输出的结果也和expect的不一样：
fab faB fa8 Fab FaB Fa8 4ab 4aB 4a8 | p*****2
发帖数: 21240 | 3
你是topdown，他是bottomup的
【在 e******i 的大作中提到】
: 另外我输出的结果也和expect的不一样：
: fab faB fa8 Fab FaB Fa8 4ab 4aB 4a8
|
|
