2019-07-05剑指 字符串的排列

2019-07-05  本文已影响0人  mztkenan

有重复字符的全排列
整整30min 。纠结的点在于如何转换为list,终止条件

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        s=list(ss)
        s.sort()
        tmp=self.permu(s)
        res=[]
        for c in tmp:
            res.append("".join(c)) #如何将结果转换为字符串
        return res


    def permu(self,s):
        if len(s)==1:return [s]  #递归的终止条件出错
        res=[]
        for i in range(len(s)):
            if i==0 or s[i]!=s[i-1]:
                for p in self.permu(s[:i]+s[i+1:]):
                    res.append([s[i]]+p)
        return res

借鉴的是原来的有些奇葩的思路

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        if not ss: return []  # 初始条件直接输入空字符串
        s=list(ss)
        s.sort()
        tmp=self.permu(s)
        res=[]
        for c in tmp:
            res.append("".join(c)) #如何将结果转换为字符串
        return res


    def permu(self,s):
        # if len(s)==1:return [s]  #递归的终止条件出错
        res=[]
        for i in range(len(s)):
            if i==0 or s[i]!=s[i-1]:
                for p in self.permu(s[:i]+s[i+1:]):
                    res.append([s[i]]+p)
        return res or [[]] # 当s为空时的巧妙的递归条件
上一篇 下一篇

猜你喜欢

热点阅读