难度: Medium
无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
示例1:
输入：S = "qwe" 输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
示例2:
输入：S = "ab" 输出：["ab", "ba"]
提示:
- 字符都是英文字母。
- 字符串长度在[1, 9]之间。
Submission
运行时间: 43 ms
内存: 21.7 MB
class Solution:
def permutation(self, S: str) -> List[str]:
res = []
s = list(S)
def dfs(x):
if x == len(s) - 1:
res.append(''.join(s))
return
dic = set()
for i in range(x, len(s)):
s[i], s[x] = s[x], s[i]
dfs(x+1)
s[i], s[x] = s[x], s[i]
dfs(0)
return res
Explain
这个题解使用了回溯算法来生成字符串的所有排列。首先，将字符串转化为字符列表，然后通过递归的深度优先搜索（DFS）方法，通过不断交换字符位置来探索所有可能的排列。具体而言，对于每个递归层，算法通过遍历从当前位置到字符串末尾的所有字符，并与当前位置的字符进行交换，来生成新的排列。交换后，算法递归到下一个位置，继续进行字符交换直到到达字符串的末尾，此时记录一个完整的排列。随后，通过回溯（即再次交换字符）恢复原字符串的顺序，以便进行后续的排列生成。
时间复杂度: O(n*n!)
空间复杂度: O(n)
class Solution:
def permutation(self, S: str) -> List[str]:
res = [] # 结果列表
s = list(S) # 将输入字符串转换为字符列表
def dfs(x):
if x == len(s) - 1: # 当递归到字符串的最后一个字符时
res.append(''.join(s)) # 将当前排列添加到结果列表
return
for i in range(x, len(s)): # 从当前位置到字符串末尾
s[i], s[x] = s[x], s[i] # 交换当前位置和i位置的字符
dfs(x+1) # 递归处理下一个位置
s[i], s[x] = s[x], s[i] # 回溯，恢复交换前的状态
dfs(0) # 从第一个位置开始递归
return res # 返回所有排列
Explore
在递归方法`dfs`中，当递归到字符串的最后一个字符时，意味着当前的字符组合已经形成了一个完整的排列，因为从字符串的第一个字符到最后一个字符的每个位置都固定了字符。此时，没有必要继续交换，因为已经达到了字符串的末尾，不存在更多的字符可以进行交换。直接将这个完整的排列添加到结果列表是合理的，因为这代表了一种独特的字符排列。
在回溯算法中，第一次交换`s[i], s[x] = s[x], s[i]`是为了将当前索引`x`的元素与循环中的索引`i`的元素交换，这样可以形成新的字符排列进入下一层递归。递归调用`dfs(x+1)`后，需要再次执行交换`s[i], s[x] = s[x], s[i]`，目的是恢复字符串到递归之前的状态。这样回溯到上一层递归时，字符串的顺序是未被改变的，确保每次递归都是从原始（或上一状态的）字符串开始，以探索所有可能的字符排列。这种方法确保了算法正确性和完整性，每次递归都能基于一个未被修改的字符序列进行。
由于题目已经明确指出字符串中的每个字符都是独一无二的，因此在使用回溯算法生成排列时，每次交换都会产生一个新的字符组合。由于每个字符只使用一次，并且每种组合都是通过交换不同位置的字符得到的，因此不可能重复生成相同的排列。再加上回溯算法通过递归和回溯确保探索了所有可能的排列方式，所以在这种情况下不需要额外的机制来防止排列的重复。每个排列都是唯一生成的，确保了输出的排列列表中不会有重复。