27 字符串的排列

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。

示例：

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

解题思路

核心思想：使用回溯法，交换字符位置生成所有排列。

关键步骤：

1. 固定第一个字符，递归求后面字符的排列
2. 交换第一个字符与后面的字符
3. 递归完成后，交换回来（回溯）

时间复杂度：O(n!) 空间复杂度：O(n)

Python 实现

def permutation(s):
    """
    求字符串的所有排列

    Args:
        s: 输入字符串

    Returns:
        list: 所有可能的排列
    """
    result = []
    s_list = list(s)

    def backtrack(start):
        # 每次递归产生一个排列
        if start == len(s_list):
            result.append(''.join(s_list))
            return

        # 固定第start位，交换后面的字符
        for i in range(start, len(s_list)):
            # 交换
            s_list[start], s_list[i] = s_list[i], s_list[start]
            # 递归
            backtrack(start + 1)
            # 回溯
            s_list[start], s_list[i] = s_list[i], s_list[start]

    backtrack(0)
    return result


# 去重版本
def permutation_unique(s):
    """
    求字符串的所有排列（去重）
    """
    result = []
    s_list = list(s)
    used = [False] * len(s_list)

    def backtrack(path):
        if len(path) == len(s_list):
            result.append(''.join(path))
            return

        for i in range(len(s_list)):
            if used[i]:
                continue

            # 去重：如果当前字符与前一个字符相同，且前一个未被使用
            if i > 0 and s_list[i] == s_list[i - 1] and not used[i - 1]:
                continue

            used[i] = True
            path.append(s_list[i])
            backtrack(path)
            path.pop()
            used[i] = False

    backtrack([])
    return result


# 测试代码
if __name__ == "__main__":
    print("abc的排列:", permutation("abc"))
    print("abc的排列（去重）:", permutation_unique("abc"))
    print("aab的排列（去重）:", permutation_unique("aab"))

# 输出:
# abc的排列: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
# abc的排列（去重）: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
# aab的排列（去重）: ['aab', 'aba', 'baa']

图解

回溯过程示例: "abc"

backtrack(0):
  i=0: 固定'a'
    backtrack(1):
      i=1: 固定'b'
        backtrack(2):
          i=2: 固定'c' → "abc"
      i=2: 交换'c','b'
        backtrack(2):
          i=2: 固定'b' → "acb"
  i=1: 交换'a','b'
    ... (类似过程)
  i=2: 交换'a','c'
    ... (类似过程)

最终: abc, acb, bac, bca, cab, cba