Given a string, find all its permutations without any repetition? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Given a string, find all its permutations without any repetition?

Given a string, find all its permutations without any repetition?# JobHunting - 待字闺中

l*r2012-12-17 08:12

1 楼

Any idea?
Especailly for the case that there are multiple same letters in the string.

c*a2012-12-17 08:12

2 楼

use hash to check duplicate?

l*b2012-12-17 08:12

3 楼

用leetcode上next permutation的办法就可以过吧
整数版本的，换成字符就好啦
vector > permute(vector &num) {
sort(num.begin(), num.end());
vector > r;
r.push_back(num);
while(nextPermute(num))
r.push_back(num);
return r;
}
bool nextPermute(vector &num) {
int i,j,n;
i = j = num.size() - 1;
while(i > 0 && num[i] <= num[i-1])
--i;
n = i - 1;
if(n < 0) return false;
else{
while(i < j)
swap(num[i++], num[j--]);
i = n + 1;
while(num[i] <= num[n])
++i;
swap(num[i], num[n]);
return true;
}
}

p*22012-12-17 08:12

4 楼

复杂度太高吧

【在 l*******b 的大作中提到】

: 用leetcode上next permutation的办法就可以过吧
: 整数版本的，换成字符就好啦
: vector > permute(vector &num) {
: sort(num.begin(), num.end());
: vector > r;
: r.push_back(num);
: while(nextPermute(num))
: r.push_back(num);
: return r;
: }

l*b2012-12-17 08:12

5 楼

嗯，我觉得差不太多，n! 和n*n!这个比较

【在 p*****2 的大作中提到】

: 复杂度太高吧