我有字符串“0011”并且希望所有组合都没有重复。 这意味着我想要一个由两个“0”和两个“1”组合而成的字符串； 例如:[0011,0101,0110,1001,1010,1100]
我试过这个，结果正是我需要的。
private void permutation(String result, String str, HashSet hashset) {
if (str.length()==0 && !hashSet.contains(result)){
System.out.println(result);
hashSet.add(result);
return;
}
IntStream.range(0,str.length()).forEach(pos->permutation(result+ str.charAt(pos), str.substring(0, pos) + str.substring(pos+1),hashset));
}
如果我删除 HashSet，此代码将产生 24 个结果而不是 6 个结果。
但是这段代码的时间复杂度是O(n!)。
如何避免创建重复字符串并降低时间复杂度？
最佳答案
可能这样的东西比 n!即使在小 n 这个想法是计算结果项中我们需要多少位，并且 遍历所有可能的值并仅过滤那些具有相同位数的值。只有一个 1 和 50%/50% 的 0 和 1 时，它将工作相似的时间
function bitCount(n) {
n = n - ((n >> 1) & 0x55555555)
n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24
}
function perm(inp) {
const bitString = 2;
const len = inp.length;
const target = bitCount(parseInt(inp, bitString));
const min = (Math.pow(target, bitString) - 1);
const max = min << (len - target);
const result = [];
for (let i = min; i < max + 1; i++) {
if (bitCount(i) === target) {
result.push(i.toString(bitString).padStart(len, '0'));
}
}
return result;
}
const inp = '0011';
const res = perm(inp);
console.log('result',res);附言我的第一个想法可能比上层代码更快。但是upper更容易实现
第一个想法是将字符串转换为整数 并使用按位左移，但每次只使用一个数字。它仍然取决于n。并且可以大于或小于上面的解决方案。但位移本身更快。
example
const input = '0011'
const len = input.length;
step1: calc number of bits = 2;
then generate first element = 3(Dec) is = '0011' in bin
step2 move last from the right bit one position left with << operator: '0101'
step3 move again: '1001'
step4: we are reached `len` so use next bit:100'1' : '1010'
step5: repeat:'1100'
step6: move initial 3 << 1: '0110'
repeat above steps: '1010'
step8: '1100'
it will generate duplicates so probably can be improved
希望对你有帮助
关于algorithm - 具有重复字符的字符串排列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55816852/