i****h
发帖数: 321 | 1 permutation of a string。但是如果string中有重复的字母怎么办？
可以用hashtable存已经生成的string，有没有不需要额外空间的办法呢？ |
H*M
发帖数: 1268 | 2 请考古
【在 i****h 的大作中提到】
: permutation of a string。但是如果string中有重复的字母怎么办？
: 可以用hashtable存已经生成的string，有没有不需要额外空间的办法呢？
|
m*****f
发帖数: 1243 | 3 这个头像好
【在 H*M 的大作中提到】
: 请考古
|
H*M
发帖数: 1268 | 4 彼此彼此...
【在 m*****f 的大作中提到】
: 这个头像好
|
a********a
发帖数: 219 | 5 我不这样认为。
现在我看你的帖子有一点心里恐惧和生理不适。你的头像严重影响了你的个人发展。
【在 H*M 的大作中提到】
: 彼此彼此...
|
i****h
发帖数: 321 | 6 老大，我知道肯定是老题。可是到哪里考啊。搜permutation也搜不到。
【在 H*M 的大作中提到】
: 请考古
|
b***e
发帖数: 1419 | 7 Brute-force based on case study directly:
a. the first letter is 'a', then do a recursive call with 1 a less;
b. the first letter is 'b', then do a recursive call with 1 b less;
..., ...
No extra space needed.
【在 i****h 的大作中提到】
: permutation of a string。但是如果string中有重复的字母怎么办？
: 可以用hashtable存已经生成的string，有没有不需要额外空间的办法呢？
|
i****h
发帖数: 321 | 8 可是如果string是aab呢？
结果是aab,aab,aba,aba,baa,baa，有重复。
怎么生成没有重复的呢？
谢谢。
【在 b***e 的大作中提到】
: Brute-force based on case study directly:
: a. the first letter is 'a', then do a recursive call with 1 a less;
: b. the first letter is 'b', then do a recursive call with 1 b less;
: ..., ...
: No extra space needed.
|
a****n
发帖数: 230 | |
i****h
发帖数: 321 | |
b***e
发帖数: 1419 | 11 The solution proposed in this link is not satisfactory. If I were the
interviewer, I will consider to fail you if you can only give this.
The reason is that the algorithm in the proposed solution is working
in time complexity of O(n!), where n is the length of the string.
This is the case even if I give you n same characters in the string,
in which case I expect you finish within linear time. |
s*****i
发帖数: 355 | 12 你给个linear time的in place算法？谢谢
【在 b***e 的大作中提到】
: The solution proposed in this link is not satisfactory. If I were the
: interviewer, I will consider to fail you if you can only give this.
: The reason is that the algorithm in the proposed solution is working
: in time complexity of O(n!), where n is the length of the string.
: This is the case even if I give you n same characters in the string,
: in which case I expect you finish within linear time.
|
r**u
发帖数: 1567 | 13 check out next_permutation function in STL
【在 i****h 的大作中提到】
: permutation of a string。但是如果string中有重复的字母怎么办？
: 可以用hashtable存已经生成的string，有没有不需要额外空间的办法呢？
|
b***e
发帖数: 1419 | 14 Here is one implemented in javascript:
var _permute = function(h, current) {
var finish = true;
for (var k in h) {
if (!h[k]) {
continue;
}
finish = false;
h[k] -= 1;
if (h[k] == 0) {
h[k] = undefined;
}
current.push(k);
_permute(h, current);
// state recover
current.pop();
if (!h[k]) {
h[k] = 0;
}
h[k]++;
}
if (finish) {
console.log(
【在 s*****i 的大作中提到】
: 你给个linear time的in place算法？谢谢
|
