l********r 发帖数: 140 | 1 Old question, but can't find a good and easy to understand answer.
What happens if there are duplicate letters in the string? like, abcdd. | p*****2 发帖数: 21240 | 2 You shouldn't output duplicate permutations. | r****c 发帖数: 2585 | 3 use recursive, fix the first letter then do permutation for the rest n-1.
【在 l********r 的大作中提到】 : Old question, but can't find a good and easy to understand answer. : What happens if there are duplicate letters in the string? like, abcdd.
| l********r 发帖数: 140 | 4 It asks to handle the case where there are duplicate letters in the input
string. | s**x 发帖数: 7506 | 5 use or implement your own std::next_permutation | x*******8 发帖数: 145 | 6
Easy way is use set, you cannot store duplicate keys in set :D
Or you can do some check, e.g aabc,
if(i>0&&str[i]==str[i-1]&&!flag[i-1]) continue;
【在 l********r 的大作中提到】 : It asks to handle the case where there are duplicate letters in the input : string.
| p*****2 发帖数: 21240 | 7 p = (x) -> console.log x
swap = (arr, i, j) -> [arr[i], arr[j]] = [arr[j], arr[i]]
dfs = (arr, curr) ->
if curr is arr.length
p arr.join("")
return
set = {}
for i in [curr...arr.length]
unless set[arr[i]]
set[arr[i]]=true
swap arr, curr, i
dfs arr, curr+1
swap arr, curr, i
permutation = (str) -> dfs str.split(""), 0 | l*n 发帖数: 529 | 8 递归并用一个Boolean[26],记录是否用过某个字符作为开头了。
【在 l********r 的大作中提到】 : Old question, but can't find a good and easy to understand answer. : What happens if there are duplicate letters in the string? like, abcdd.
| h**o 发帖数: 548 | 9 我用swap那种解法理解的。去duplicate就加上noswap()判断。
bool noswap(int level, int i, const vector& num){
for (int j=level;j
if (num[j]==num[i]){
return true;
}
}
return false;
}
void perm_recur(vector &num, int size, int level, vector
> >& results) {
if (level == size) {results.push_back(num); return;}
for (int i = level; i < size; i++){
if (noswap(level, i, num)) continue;
swap(num[level], num[i]);
perm_recur(num, size, level+1, results);
swap(num[level], num[i]);
}
}
【在 l********r 的大作中提到】 : Old question, but can't find a good and easy to understand answer. : What happens if there are duplicate letters in the string? like, abcdd.
|
|