问一道题的优化以及时间复杂度# JobHunting - 待字闺中
e*i
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
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时间复杂度该怎么算
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
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
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时间复杂度该怎么算
