题⽬描述

输⼊⼀个字符串，按字典序打印出该字符串中字符的所有排列。例如输⼊字符串 abc，则按字典序打印出由字符 a , b , c 所能排列出来的所有字符串 abc , acb , bac , bca , cab 和 cba 。

输⼊描述：输⼊⼀个字符串，⻓度不超过9(可能有字符重复)，字符只包括⼤⼩写字⺟

思路及解答

在看回溯系列算法题时，可以先学习整体框架：回溯算法

回溯+剪枝法（优化去重）

上面方法主要是通过Set进行去重，也可以将字符数组排序来跳过重复字符：

  1. 先排序​：将字符数组排序，使相同字符相邻

  2. 剪枝策略​：在递归过程中跳过相同字符的重复分支

  3. 标记数组​：使用boolean数组记录已使用字符

  • 时间复杂度​：O(n*n!)，但剪枝减少了不必要的递归调用

  • 空间复杂度​：O(n!)，结果存储空间

非递归

此方法算法理解难度较大，非标准解法

用字典序生成下一个排列的算法：

  1. 初始排序​：将字符数组按字典序排序

  2. 找下一个排列​：

  • 从后向前找到第一个升序对

  • 交换适当元素

  • 反转后缀

  1. 循环生成​：直到无法生成下一个排列

  • 时间复杂度​：O(n*n!)，每次生成下一个排列需要O(n)时间

  • 空间复杂度​：O(n!)，结果存储空间