当前位置： 面试刷题>> 字符串的不同排列 (经典算法题500道)
### 题目描述
**题目**：给定一个字符串`s`，请编写一个函数来生成该字符串的所有不同排列，并以列表的形式返回这些排列。注意，结果中的排列顺序不重要，但每个排列中的字符顺序必须保持原字符串中的相对顺序。
### 示例
**输入**：`s = "abc"`
**输出**：`["abc", "acb", "bac", "bca", "cab", "cba"]`
### 解答
下面分别给出PHP、Python和JavaScript的示例代码：
#### PHP 示例
```php
function permuteUnique($s) {
$result = [];
$strArr = str_split($s);
sort($strArr); // 排序，为了后续去重
$used = array_fill(0, count($strArr), false);
backtrack($strArr, $used, '', $result);
return $result;
}
function backtrack(&$strArr, &$used, $current, &$result) {
if (strlen($current) == count($strArr)) {
$result[] = $current;
return;
}
for ($i = 0; $i < count($strArr); $i++) {
// 跳过重复字符和已使用的字符
if ($i > 0 && $strArr[$i] == $strArr[$i-1] && !$used[$i-1]) {
continue;
}
if (!$used[$i]) {
$used[$i] = true;
backtrack($strArr, $used, $current . $strArr[$i], $result);
$used[$i] = false;
}
}
}
// 测试
$s = "abc";
$output = permuteUnique($s);
print_r($output);
```
#### Python 示例
```python
def permuteUnique(s):
def backtrack(first=0):
if first == n:
output.append(''.join(s))
for i in range(first, n):
# 避免产生重复的排列
if i > first and s[i] == s[first]:
continue
s[first], s[i] = s[i], s[first]
backtrack(first + 1)
s[first], s[i] = s[i], s[first]
s = sorted(s)
n = len(s)
output = []
backtrack()
return output
# 测试
s = "abc"
print(permuteUnique(s))
```
#### JavaScript 示例
```javascript
function permuteUnique(s) {
const result = [];
const strArr = s.split('');
strArr.sort((a, b) => a.localeCompare(b)); // 排序，用于去重
const used = new Array(strArr.length).fill(false);
function backtrack(first = 0) {
if (first === strArr.length) {
result.push(strArr.join(''));
return;
}
for (let i = first; i < strArr.length; i++) {
// 跳过重复和已使用的字符
if (i > first && strArr[i] === strArr[first] && !used[first]) continue;
if (!used[i]) {
[strArr[first], strArr[i]] = [strArr[i], strArr[first]];
used[i] = true;
backtrack(first + 1);
used[i] = false;
[strArr[first], strArr[i]] = [strArr[i], strArr[first]];
}
}
}
backtrack();
return result;
}
// 测试
const s = "abc";
console.log(permuteUnique(s));
```
**码小课网站中有更多相关内容分享给大家学习**，可以探索更多算法和数据结构的知识。