字符串的排列_

推荐

Java

偏北

 /**
     * 1、递归算法
     *
     * 解析：http://www.cnblogs.com/cxjchen/p/3932949.html  (感谢该文作者！)
     *
     * 对于无重复值的情况
     *
     * 固定第一个字符，递归取得首位后面的各种字符串组合；
     * 再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合； *递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
     *
     * 假如有重复值呢？
     * *由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。
     * 例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。
     * 但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。
     * 由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。
     *
     * 换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，
     * 所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！
     *
     *
     * @param str
     * @return
     */

public ArrayList<String> Permutation(String str){

        ArrayList<String> list = new ArrayList<String>();
        if(str!=null && str.length()>0){
            PermutationHelper(str.toCharArray(),0,list);
            Collections.sort(list);
        }
        return list;
    }
    private void PermutationHelper(char[] chars,int i,ArrayList<String> list){
        if(i == chars.length-1){
            list.add(String.valueOf(chars));
        }else{
            Set<Character> charSet = new HashSet<Character>();
            for(int j=i;j<chars.length;++j){
                if(j==i || !charSet.contains(chars[j])){
                    charSet.add(chars[j]);
                    swap(chars,i,j);
                    PermutationHelper(chars,i+1,list);
                    swap(chars,j,i);
                }
            }
        }
    }

    private void swap(char[] cs,int i,int j){
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }

/**
     * 2、字典序排列算法
     *
     * 可参考解析： http://www.cnblogs.com/pmars/archive/2013/12/04/3458289.html  （感谢作者）
     *
     * 一个全排列可看做一个字符串，字符串可有前缀、后缀。
     * 生成给定全排列的下一个排列.所谓一个的下一个就是这一个与下一个之间没有其他的。
     * 这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。
     *
     * [例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的987654321，
     * 从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。
     *
     * 【例】 如何得到346987521的下一个
     * 1，从尾部往前找第一个P(i-1) < P(i)的位置
     * 3 4 6 <- 9 <- 8 <- 7 <- 5 <- 2 <- 1
     * 最终找到6是第一个变小的数字，记录下6的位置i-1
     *
     * 2，从i位置往后找到最后一个大于6的数
     * 3 4 6 -> 9 -> 8 -> 7 5 2 1
     * 最终找到7的位置，记录位置为m
     *
     * 3，交换位置i-1和m的值
     * 3 4 7 9 8 6 5 2 1
     * 4，倒序i位置后的所有数据
     * 3 4 7 1 2 5 6 8 9
     * 则347125689为346987521的下一个排列
     *
     * @param str
     * @return
     */

public ArrayList<String> Permutation2(String str){
        ArrayList<String> list = new ArrayList<String>();
        if(str==null || str.length()==0){
            return list;
        }
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        list.add(String.valueOf(chars));
        int len = chars.length;
        while(true){
            int lIndex = len-1;
            int rIndex;
            while(lIndex>=1 && chars[lIndex-1]>=chars[lIndex]){
                lIndex--;
            }
            if(lIndex == 0)
                break;
            rIndex = lIndex;
            while(rIndex<len && chars[rIndex]>chars[lIndex-1]){
                rIndex++;
            }
            swap(chars,lIndex-1,rIndex-1);
            reverse(chars,lIndex);

            list.add(String.valueOf(chars));
        }

        return list;
    }

    private void reverse(char[] chars,int k){
        if(chars==null || chars.length<=k)
            return;
        int len = chars.length;
        for(int i=0;i<(len-k)/2;i++){
            int m = k+i;
            int n = len-1-i;
            if(m<=n){
                swap(chars,m,n);
            }
        }

    }

编辑于 2018-12-26 14:11:30 回复(38)

Python

Dinochang

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        res = []
        length = len(ss)
        visited = [False for _ in range(length)] 
        path = []
        
        def dfs(ss, length):
            if len(path) == length:
                temp = "".join(path)
                if temp not in res:
                    res.append(temp)
                return None
            
            for i in range(length):
                if not visited[i]:
                    path.append(ss[i])
                    visited[i] = True
                    dfs(ss, length)
                    path.pop()
                    visited[i] = False 
                    
        dfs(ss, length)
        return res

发表于 2022-04-08 20:59:41 回复(0)

Python

牛客541273514号

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        if not ss:
            return None
        if len(ss)==1&nbs***bsp;set(ss)==1:
            return [ss]
        res=[]
        for i in range(len(ss)):
            s1=ss[i]
            s2=ss[0:i]+ss[i+1:]
            for item in self.Permutation(s2):
                res.append(s1+item)
                res.append(item+s1)
        res=set(res)
        res=list(res)
        res=sorted(res)
        return res

发表于 2021-04-20 21:27:31 回复(0)

Python

Hiroi

思路：1. 递归找出所有组合；2. 消除重复元素；3. 排序。

# -*- coding:utf-8 -*-
class Solution:
    def Allstring(self, ss):
        results = []
        for i in range(len(ss)):
            temp1 = ss[i]
            temp2 = ss[:i] + ss[i + 1:]
            temp3 = self.Allstring(temp2)
            if temp3:
                for x in temp3:
                    results.append(temp1 + x)
            else:
                results.append(temp1)
        return results
    
    def Permutation(self, ss):
        # write code here
        # get all string 
        result = self.Allstring(ss)
        result = list(set(result))
        result.sort()
        return result

发表于 2021-04-16 17:24:44 回复(0)

Python

行走的三百斤

依次键入字符，如 [['a']] 中插入 ‘b’ , 结果 [['a', 'b'], ['b', 'a']] 再键入 'c'，根据不同位置，返回 [['c', 'b', 'a'], ['b', 'c', 'a'], ['b', 'a', 'c'], ['c', 'a', 'b'], ['a', 'c', 'b'], ['a', 'b', 'c']]。

因为存在相同字符的情况，通过 in 方法判断，或者在结束时，使用set过滤。

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        if len(ss) == 1:
            return [ss]
        if len(ss) == 2:
            return list(set([ss[::1], ss[::-1]]))
        temp = [[ss[0]]]
        for i in range(1, len(ss)):
            temp = self.getDefStr(temp, ss[i])
        return sorted([''.join(i) for i in temp])


    def getDefStr(self, temp, s):
        if not temp:
            temp.append(s)
            return temp
        res = []
        for cur in temp:
            for i in range(len(cur) + 1):
                temp1 = cur[:]
                temp1.insert(i, s)
                if temp1 not in res:
                    res.append(temp1)
        return res

发表于 2021-03-31 10:28:35 回复(0)

Python

爱睡懒觉的帕丁顿

class Solution:
def Permutation(self, ss):
# write code here
all_list = []
def dfs(remain,current):
if remain=='' and current not in all_list:
all_list.append(current[:])
for i in range(len(remain)):
tmp = remain[0:i]+remain[i+1:]
dfs(tmp,current+remain[i])
dfs(ss,'')
return all_list

发表于 2021-03-13 21:15:23 回复(0)

Python

cantonhannibal

假定可以生成前n-1个字符的排列，即可生成前n个字符的排列。

生成s[1:n]的排列，在每个排列前加上s[0];

生成s[1,3,4:n]的排列，在每个排列前加上s[2];

...

重复上述步骤直到生成s[1:n-1]的全部排列,并在每个排列前面加上n

class Solution:
def __init__(self):
self.p=list()
self.result=list()
def perl(self,m):
if m==len(self.p)-1:
s= ''.join(self.p)
if s not in self.result:#如果不存在才加入
self.result.append(s)
else:
for j in range(m,len(self.p)):
self.p[j],self.p[m] = self.p[m],self.p[j] #0-0、 0-1、0-2...1-0、1-1、1-2...互换
self.perl(m+1)
self.p[j],self.p[m]= self.p[m],self.p[j]#每换完一轮要换回来，再进行下一个字符的排列
def Permutation(self, s):
self.p=list(s)
self.perl(0)
self.result.sort()#按照字典排序
return self.result
若字符串长度为n且无重复字符,则有n!个排列，递归步骤要执行nn!次，时间复杂度为Θ(nn!)

编辑于 2020-11-16 01:33:44 回复(0)

Python

RyuAsuka

# -*- coding:utf-8 -*-
import itertools
class Solution:
    def Permutation(self, ss):
        results = []
        if ss == '':
            return results
        for i in itertools.permutations(ss, len(ss)):
            results.append(''.join([x for x in i]))
        results = list(set(results))
        results.sort()
        return results

python 直接可以用 itertools.permutations函数

发表于 2020-10-23 10:10:14 回复(0)

Python

eastzzp

# -*- coding:utf-8 -*-
import copy
class Solution:

    
    def Permutation(self, ss):
        if not ss:
            return []
        def recu(str,tmtmp):        
            for s in str:
                tmp = copy.copy(tmtmp)
                tmp = tmp+s
                strtmp = copy.copy(str)
                strtmp.remove(s)
                if(len(strtmp)==0):
                    res.append(tmp)
                    tmp = ''
                    return
                recu(strtmp,tmp)
        
        ss = list(ss)
        tmp = ''
        res = []
        recu(ss,tmp)
        return sorted(set(res))

发表于 2020-09-16 16:53:34 回复(0)

Python

sk8_wt

class Solution:
    def Permutation(self, ss):
        if len(ss) <= 1:
            return ss
        if len(ss) <= 2:
            return sorted(list(set([ss,ss[1]+ss[0]])))
        list_ = []
        for i in range(len(ss)):
            first = ss[i]
            for i in self.Permutation(ss[:i]+ss[i+1:]):
                list_.append(first+i)
        return sorted(list(set(list_)))

发表于 2020-08-08 21:59:17 回复(0)

Python

DDooo

# -*- coding:utf-8 -*-
import itertools
class Solution:
    def Permutation(self, ss):
        # write code here
        if not ss:
            return []
        return sorted(list(set(map("".join, itertools.permutations(ss)))))

1，map:会根据提供的函数对指定序列做映射。

2，set:创建一个无序不重复元素集。

3，list：方法用于将元组转换为列表。

4，sorted:对列表排序。

发表于 2020-07-29 20:03:08 回复(0)

Python

牛客720457535号

用排列组合的方法求解

借鉴了动态规划的思想拆分出子问题，一个字符串'abc',可拆成'ab'和'c','ab'本身有两种组合'ab'和'ba'，对于每一种组合'c'有3个位置可以插。
同理对于长度为n的字符串，从第一个字符开始重复上述操作，递归到最后一个字符为止。
对于重复的问题可用set()解决

# -*- coding:utf-8 -*-
import copy
class Solution:
    def Permutation(self, ss):
        # write code here
        # 边界情况
        if ss == None:
            return
        if len(ss) == 1 or len(ss) == 0:
            return ss

        ss = list(ss)
        totalCombine = [ss[0]]
        for i in range(1, len(ss)):
            tmpCombine = []
            s = ss[i]

            for cmb in totalCombine:
                # 将字符串打散成单个字母的list
                cmb = list(cmb)
                tmp = copy.deepcopy(cmb)
                # 新增字符插入n+1个不同位置
                for j in range(len(cmb) + 1):
                    cmb = copy.deepcopy(tmp)
                    cmb.insert(j, str(s))
                    tmpCombine.append(''.join(cmb))
            totalCombine = copy.deepcopy(tmpCombine)

        # 去重
        totalCombine = sorted(list(set(totalCombine)))
        return totalCombine

发表于 2020-07-22 11:53:09 回复(0)

Python

牛客473055830号

# -*- coding:utf-8 -*-
class Solution:
    
    def demo(self, s, rs, r):
        if len(s) == 1:
            rs += s[0]
            r.append(rs)
            return
        for i in range(len(s)):
            rs_t = rs + s[i]
            st = s[:]
            del st[i]
            self.demo(st[:], rs_t, r)
    
    def Permutation(self, ss):
        # write code here
        if not ss&nbs***bsp;len(ss) == 1:
            return ss
        rl = []
        ss = list(ss)
        self.demo(ss[:], '', rl)
        rl = list(set(rl))
        rl.sort()
        return rl

发表于 2020-05-28 23:04:43 回复(0)

Python

牛客616582550号

num ='abc'
for i in num:
    for j in num:
        for m in num:
            if i!=j and i!=m and j!=m:
                print(i,j,m)

发表于 2020-05-12 09:04:30 回复(0)

Python

peter-xbs

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        strset = set()
        for c in ss:
            if not strset:
                strset.add(c)
            else:
                tmp_set = set()
                for item in strset:
                    for i in range(len(item)+1):
                        tmp = item[:i]+c+item[i:]
                        tmp_set.add(tmp)
                strset = tmp_set

硬算 24ms，来找更佳答案

编辑于 2020-03-24 23:03:03 回复(0)

Python

牛客110142340号

Python

对着那张图recursion tree的图写，两个循环外循环遍历树的深度内循环遍历每一层的节点。

每一层字母交换完毕后将结果作为下一层的输入。

新人***写的，代码比较累赘

import copy

class Solution:
    def Permutation(self, ss):
        if not ss:
            return []
        elif len(ss) == 1:
            return ss
        else:
            ss = list(ss)
            arr1 = [ss]
            for k in range(len(ss), 1, -1):
                arr3 = []
                for j in arr1:
                    j = list(j)
                    arr2 = self.se(j, k)
                    for el in arr2:
                        arr3.append(el)
                arr1 = copy.deepcopy(arr3)
            arr1 = list(set(arr1))
            arr1.sort()
            return arr1

    def se(self, ss, k):
        arr = []
        st = ss[:k]
        sr = ss[k:]
        for k2 in range(len(st)-1, -1, -1):
            ss1 = self.swap(-1, st, k2)
            ss2 = ''.join(ss1) + ''.join(sr)
            arr.append(ss2)
        return arr

    def swap(self, k1, ss, k2):
        tt = copy.deepcopy(ss)
        tmp = tt[k2]
        tt[k2] = tt[k1]
        tt[k1] = tmp
        return tt

发表于 2020-03-17 18:29:56 回复(0)

Python

柴柴总

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.result = list()

    def Permutation(self, ss):
        if len(ss) == 0:
            return []
        ss_list = list()
        for s in ss:
            ss_list.append(s)
        self.Digui(ss_list, 0)
        self.resort(self.result)
        return self.result

    def Digui(self, ss, i):
        if i == len(ss) - 1:
            self.result.append("".join(ss))
            return
        else:
            j = i
            while j < len(ss):
                if self.repeat(ss, i, j) == False:
                    self.change(ss, i, j)
                    self.Digui(ss, i + 1)
                    self.change(ss, j, i)


                j += 1

    def resort(self, ss):
        for i in range(0, len(ss)):
            for j in range(i, len(ss)):
                if ss[j] < ss[i]:
                    self.change(ss, i, j)


        # write code here

    def change(self, ss, i, j):
        temp = ss[i]
        ss[i] = ss[j]
        ss[j] = temp

    def repeat(self, ss, i, j):
        while(i < j):
            if ss[i] == ss[j]:
                return True
            i += 1
        return False

编辑于 2020-02-19 01:37:56 回复(0)

Python

andycruz

递归法和回溯法的Python实现

参考讨论区用Python实现了两种方法。

递归法：

class Solution:
    def Permutation(self, ss):
        if len(ss) <= 1:
            return ss
        res = set()
        for i in range(len(ss)):
			# 每一个j是Permutation(ss[:i]+ss[i+1:])这个list中不同排列组合的一个string
            for j in self.Permutation(ss[:i]+ss[i+1:]):
                res.add(ss[i]+j)
        return sorted(res)

回溯法：

class Solution:
    def Permutation(self, ss):
        if len(ss) <= 1:
            return ss
        res=set()
        tmp=[]
		# 用一个dict记住每个单词出现次数
        n_dict = dict((x,0) for x in ss)
        for s in ss:
            n_dict[s]+=1
        self.Back(res,tmp,ss,n_dict)
        return sorted(list(res))
    def Back(self,res,tmp,ss,counter):
        if len(tmp) == len(ss):
            print(tmp)
            print(len(ss))
            res.add(''.join(tmp))
        else:
            for i in ss:
                if counter[i] == 0:
                    continue
                # 用一次就减一，回溯时记得加回来
				counter[i] -= 1
                tmp.append(i)
                self.Back(res,tmp,ss,counter)
                counter[i] += 1
                tmp.pop()

编辑于 2020-02-17 02:52:41 回复(0)

Python

菜鸡上路（已消毒）

参考别人的回溯法，有点麻烦，还有一个判断重复的条件🤤

class Solution:
    def Permutation(self,ss):
        # write code here  回溯法
        if len(ss)==0:
            return []
        ss = list(ss)
        res = []
        self.helper(ss,[],res)
        return res
    
    def helper(self,array,solution,res):
        if len(array)==0:
            s = "".join(solution)
            if s not in res:
                res.append(s)
            return
        for i in range (len(array)):
            newarray=array[:i]+array[i+1:]#删除第一个元素
            newsolution=solution+[array[i]]#加入新元素
            self.helper(newarray,newsolution,res)#寻找剩余元素的排列组合

发表于 2020-02-08 17:57:20 回复(0)

Python

天山剑客

# -*- coding:utf-8 -*-
# 解题思路：递归法实现字符串全排列
# 第一步：使用交换法，第一位字符和每个字符交换
# 第二步：递归实现从第二位到最后的全排列
# 第三步：交换之后复位，进行下一位交换
# 边界条件： begin == end&nbs***bsp;begin == end - 1
# 使用set进行排查，使用sort函数按字典顺序排序
class Solution:
    def Permutation(self, ss):
        # write code here
        if ss == '':
            return []

        ls = list(ss)
        start = 0
        ln = len(ls)
        res = []

        def permutation(lss, position, end):
            if position == end:
                res.append(''.join(lss))

            for index in range(position, end):
                lss[position], lss[index] = lss[index], lss[position]
                permutation(lss, position + 1, end)
                lss[index], lss[position] = lss[position], lss[index]

        permutation(ls, start, ln)
        res = list(set(res))
        res = sorted(res)
        return res

发表于 2020-01-19 15:04:23 回复(0)

Python

秋水中的鱼

经典的全排列问题

采用dfs进行回溯，为避免重复字符要进行剪枝处理

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        if not ss:
            return []
        
        #按字母顺序排序，为后面重复字符不重复计算做准备
        l=list(ss)
        l.sort()
        ss=''.join(l)
        
        #dfs初始条件
        visited=set()
        res=[]
        
        #采用深度优先遍历
        def dfs(visited,ss,t):
            #结束条件
            if len(t)==len(ss):
                res.append(t)
                return
            for i in range(len(ss)):
                if i in visited:
                    continue
                #避免重复计算
                if i-1>=0 and i-1 not in visited and ss[i]==ss[i-1]:
                    continue
                visited.add(i)
                dfs(visited,ss,t+ss[i])
                visited.remove(i)
        
        #运行dfs
        dfs(visited,ss,'')
        return res

发表于 2019-11-02 15:00:43 回复(0)

字符串的排列

输入描述:

输入

输出

说明

输入

输出

输入

输出

输入

输出

用排列组合的方法求解

递归法和回溯法的Python实现

递归法：

回溯法：

问题信息

热门推荐

通过挑战的用户

相关试题