剑指offer 字符串的排列

Posted on |

字符串的排列

题目

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

方法

方法1：剑指offer官方方法

做法是把对字符串中的每个元素都当做起始位置，把其他元素当做以后的位置，然后再同样的进行操作。这样就会得到全排列。

这个题不使用index的原因是，我们认为已经遍历过了的元素过滤掉了，只留下了未遍历的剩余的字符串当做ss。因此，所有的元素遍历完成了，ss也就是空了，就可以结束了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        output=[]
        if ss:
            self.dfs(ss,'',output)
        return sorted(list(set(output)))
    def dfs(self,ss,path,output):
        if not ss:
            output.append(path)
        else:
            for i,s in enumerate(ss):
                self.dfs(ss[:i]+ss[i+1:],path+s,output)
# dfs([1, 2, 3], [], [])
# dfs([2, 3], [1], [])
# dfs([2, 3], [1], [])
# dfs([3], [1, 2], [])
# dfs([3], [1, 2], [])
# dfs([], [1, 2, 3], [])
# dfs([], [1, 2, 3], [])
# [1, 2, 3]
# --------------------
# --------------------
# dfs([2], [1, 3], [[1, 2, 3]])
# dfs([2], [1, 3], [[1, 2, 3]])
# dfs([], [1, 3, 2], [[1, 2, 3]])
# dfs([], [1, 3, 2], [[1, 2, 3]])
# [1, 3, 2]
# --------------------
# --------------------
# --------------------
# dfs([1, 3], [2], [[1, 2, 3], [1, 3, 2]])
# dfs([1, 3], [2], [[1, 2, 3], [1, 3, 2]])
# dfs([3], [2, 1], [[1, 2, 3], [1, 3, 2]])
# dfs([3], [2, 1], [[1, 2, 3], [1, 3, 2]])
# dfs([], [2, 1, 3], [[1, 2, 3], [1, 3, 2]])
# dfs([], [2, 1, 3], [[1, 2, 3], [1, 3, 2]])
# [2, 1, 3]
# --------------------
# --------------------
# dfs([1], [2, 3], [[1, 2, 3], [1, 3, 2], [2, 1, 3]])
# dfs([1], [2, 3], [[1, 2, 3], [1, 3, 2], [2, 1, 3]])
# dfs([], [2, 3, 1], [[1, 2, 3], [1, 3, 2], [2, 1, 3]])
# dfs([], [2, 3, 1], [[1, 2, 3], [1, 3, 2], [2, 1, 3]])
# [2, 3, 1]
# --------------------
# --------------------
# --------------------
# dfs([1, 2], [3], [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]])
# dfs([1, 2], [3], [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]])
# dfs([2], [3, 1], [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]])
# dfs([2], [3, 1], [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]])
# dfs([], [3, 1, 2], [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]])
# dfs([], [3, 1, 2], [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]])
# [3, 1, 2]
# --------------------
# --------------------
# dfs([1], [3, 2], [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]])
# dfs([1], [3, 2], [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]])
# dfs([], [3, 2, 1], [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]])
# dfs([], [3, 2, 1], [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]])
# [3, 2, 1]
# --------------------
# --------------------
# --------------------
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

方法2：回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        output,tmp=[],[]
        if ss:
            self.backtrack(ss,tmp,output)
        return output

    def backtrack(self,ss,tmp,output):
        if len(tmp)==len(ss):
            output.append(tmp)
        else:
            for s in ss:
                if s in tmp:
                    continue
                tmp.append(s)
                self.backtrack(ss,tmp,output)
                tmp.pop()