题目描述

题目：给定一个字符串s，请编写一个函数来生成该字符串的所有不同排列，并以列表的形式返回这些排列。注意，结果中的排列顺序不重要，但每个排列中的字符顺序必须保持原字符串中的相对顺序。

示例

输入：s = "abc"

输出：["abc", "acb", "bac", "bca", "cab", "cba"]

解答

下面分别给出PHP、Python和JavaScript的示例代码：

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 示例

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 示例

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));

码小课网站中有更多相关内容分享给大家学习，可以探索更多算法和数据结构的知识。