w**********4
发帖数: 157 | 1 输入是 一个 String s， S中 可能含有 “*”. "*" 可以被替换成1 或者 0
For example ： "*" output "1", "0".
当时写了下面这个方法。
public static Collection getAllDecodes(String input) {
Collection list = new ArrayList();
list.add(input);
while (list.size() != 0) {
Collection res = new ArrayList();
for (String str : list) {
if (str.contains("*")) {
res.add(str.replaceFirst("\*", "1"));
res.add(str.replaceFirst("\*", "0"));
}
}
if (res.size() != 0) {
list = res;
} else {
return list;
}
}
return list;
}
这个方法的时间复杂度是O（2^n). 所有面试官问如果输串中有2^80 个 “*” 这个方
法就解决不了问题了。
所有想问一下，有什么好的方法可以处理长串输入情况。
谢谢大家。 | z***b
发帖数: 127 | 2 1. 首先找出string中有*的所有index.比如有三个*，位置是 1， 3， 5.
2. 然后把从000开始 加一，一直加到111，没此一次加一就把相应索引的字符替换一下
并且输出。
这样空间开销应该是const的。 |
|
