Sui Xin's Blog

[剑指Offer]字符串的排列

Posted on In Disqus:

题目描述

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

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

解题思路

  1. 大神写的优质代码。函数内部递归的思想，对原字符串进行遍历，递归剩余的字符，将结果添加到列表中，最后去重排序。
  2. 自己写的拙劣代码。对原序列进行遍历，将序列和遍历的字符输入另一个函数，该函数主要实现对剩余字符串的所有可能情况进行递归，最后去重和排序。实际上主要拙劣在本来一个函数可以解决的事情写了两个函数、去重的循环太多余了。

代码

Python(2.7.3)

大神写的优质代码

1
2
3
4
5
6
7
8
9
10
11
12
13
# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        if not ss:
            return []
        if len(ss) == 1:
            return [ss]
        res = []
        for i in range(len(ss)):
            for j in self.Permutation(ss[:i] + ss[i + 1:]):
                res.append(ss[i] + j)
        # set用来去重，sorted用来排序
        return sorted(set(res))

运行时间：28ms
占用内存：5752k

自己写的拙劣代码

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
# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        res = []
        for i in ss:
            if self.perm(ss, i):
                for j in self.perm(ss, i):
                    res.append(i + j)
            else:
                res.append(i)
        # 这里使用set函数去重更佳
        for i in res[:]:
            while res.count(i) > 1:
                res.remove(i)
        return sorted(res)
    
    def perm(self, ss, first):
        ss = ss.replace(first, '', 1)
        if len(ss) == 1:
            return [ss]
        res = []
        for j in ss:
            for k in self.perm(ss, j):
                res.append(j + k)
        return res

运行时间：34ms
占用内存：5856k

Related Posts