首页 > 试题广场 >

字符串的排列

[编程题]字符串的排列
  • 热度指数:923884 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
输入一个长度为 n 字符串,打印出该字符串中字符的所有排列,你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

数据范围:
要求:空间复杂度 ,时间复杂度

输入描述:
输入一个字符串,长度不超过10,字符只包括大小写字母。

示例1

输入

"ab"

输出

["ab","ba"]

说明

返回["ba","ab"]也是正确的         
示例2

输入

"aab"

输出

["aab","aba","baa"]
示例3

输入

"abc"

输出

["abc","acb","bac","bca","cab","cba"]
示例4

输入

""

输出

[""]
class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        if(str.size() == 0) return res;
        func1(res , str , 0);
        sort(res.begin() , res.end());
        return res;
    }
    
    void func1(vector<string> &res , string str , int k){
        if(k + 1 == str.size()){
            res.push_back(str);
            return;
        }
        for(int i = k; i < str.size(); i++){
            // 相同的字符不进行交换,直接跳过
            if(i != k && str[i] == str[k]) continue;
            swap(str[k] , str[i]);
            func1(res , str , k + 1);
            swap(str[k] , str[i]); // 复位
        }
    }
};
发表于 2019-07-10 22:08:52 回复(0)
更多回答
推荐
 /**
     * 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)
# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        if not ss:
            return []
        if len(ss) == 1:
            return [ss]
        ret = []
        #遍历字符串,固定第一个元素,然后递归求解
        for i in range(len(ss)):
            for j in self.Permutation(ss[:i]+ss[i+1:]):
                ret.append(ss[i]+j)
        #通过set进行去重,sorted进行重新排序
        return sorted(list(set(ret))) 
发表于 2018-04-08 09:52:05 回复(2)
/*
*字典排序算法
*一个全排列可看做一个字符串,字符串可有前缀、后缀。
*生成给定全排列的下一个排列.所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀,也即变化限制在尽可能短的后缀上。
*[例]839647521是1--9的排列。1—9的排列最前面的是123456789,最后面的987654321,从右向左扫描若都是增的,就到了987654321,也就没有下一个了。否则找出第一次出现下降的位置。
* 【例】 一般而言,设P是[1,n]的一个全排列。
*      P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn
*    find:  j=max{i|Pi<Pi+1}
*         k=max{i|Pi>Pj}
*      1,  对换Pj,Pk,
*      2,  将Pj+1…Pk-1PjPk+1…Pn翻转
*          P’= P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一个  
*【例】 如何得到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的下一个排列
*/

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public ArrayList<String> Permutation(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;
//从右往左,找到每一个开始变小数字的位置
            while(lIndex>0 && chars[lIndex-1]>=chars[lIndex]) {
                lIndex--;
            }
//从右向左扫描若都是增的,代表全排列结束
            if(lIndex == 0) {
                break;
            }
            int rIndex = lIndex;
//从开始变小数字后面开始向右遍历,找到最后一个比这个数字大的数
            while(rIndex<len && chars[rIndex]>chars[lIndex-1]) {
                rIndex++;
            }
//交换lIndex-1和rIndex-1这两个数的位置
            swap(chars,lIndex-1,rIndex-1);
//lIndex开始逆序
            reverse(chars,lIndex);
            
            list.add(String.valueOf(chars));
        }
        
        return list;
    }
    
    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
    
    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;
            swap(chars,m,n);
        }
    } 
}


/*
*递归算法
*于无重复值的情况
*1、定第一个字符,递归取得首位后面的各种字符串组合;
*2、再把第一个字符与后面每一个字符交换,并同样递归获得首位后面的字符串组合; 
*递归的出口,就是只剩一个字符的时候。
*递归的循环过程,就是从每个子串的第二个字符开始依次与第一个字符交换,然后继续处理子串。
*假如有重复值呢?
*由于全排列就是从第一个数字起,每个数分别与它后面的数字交换,我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。     
*例如abb,第一个数与后面两个数交换得bab,bba。然后abb中第二个数和第三个数相同,就不用交换了。
*由于这里的bba和开始第一个数与第三个数交换的结果相同了,因此这个方法不行。     
*换种思维,对abb,第一个数a与第二个数b交换得到bab,然后考虑第一个数与第三个数交换,此时由于第三个数等于第二个数,
*所以第一个数就不再用与第三个数交换了。再考虑bab,它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕!
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Set;
import java.util.HashSet;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> list = new ArrayList<String>();
        if(str != null && str.length()>0) {
            PermutationHelp(str.toCharArray(),0,list);
            Collections.sort(list);
        }
        
        return list;
    }
    
    public void PermutationHelp(char[] chars, int i, ArrayList<String> list) {
        if(i == chars.length-1) {
            list.add(String.valueOf(chars));
        } else {
            Set<Character> set = new HashSet<Character>();//去掉重复交换的字符
            for(int j=i; j<chars.length; j++) {
                if(j==i || !set.contains(chars[j])) {
                    set.add(chars[j]);
                    swap(chars,i,j);//交换第一个字符与其它每个字符的位置
                    PermutationHelp(chars,i+1,list);
                    swap(chars,i,j);//为了防止重复的情况,还需要将begin处的元素重新换回来
                }
            }
        }
    }
    
    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
    
    
}
发表于 2017-03-13 15:26:05 回复(0)
//简短的AC代码。调用了STL的next_permutation函数
 vector<string> Permutation(string str) {
        vector<string> answer;
        if(str.empty())
            return answer;        
        sort(str.begin(),str.end());
        do{
            answer.push_back(str);
        }
        while(next_permutation(str.begin(),str.end()));
        return answer;
}

编辑于 2015-07-11 09:28:50 回复(14)
class Solution {
public:
void solve(vector<string> &ans, string &str, int pos, int arr[], int n){
    if(pos == n){
        string tmp = "";
        int flag = 1;
        for(int i=0;i<pos;i++) tmp += str[arr[i]];
        for(int i=0;i<ans.size();i++) if(tmp == ans[i]) flag = 0;
        if(flag) ans.push_back(tmp);
    }
    else for(int i=0;i<str.length();i++){
        int ok = 1;
        for(int j=0;j<pos;j++)
            if(arr[j] == i) ok = 0;
        if(ok){
            arr[pos] = i;
            solve(ans, str, pos+1, arr, n);
        }
    }
}

    vector<string> Permutation(string str) {
        sort(str.begin(), str.end());
        vector<string> ans; int s[10];
        if(!str.empty()) solve(ans, str, 0, s, str.length());
        return ans;
    }
};
发表于 2018-12-06 16:01:00 回复(0)
//参照剑指offer的思路
class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        if(str.empty())
            return res;
        string tmp="";
        recur(str,res,tmp,0);
        return res;
    }
    void recur(string str,vector<string> &res,string &tmp,int start){
        if(start==str.size()){
            res.push_back(tmp);
            return;
        }    
        for(int i=start;i<str.size();i++){
            //判断要交换的字符是否相同,相同就不用交换直接跳过(除了start位置与自己交换的情况)
            if(i!=start&&str[start]==str[i])
                continue;
            swap(str[start],str[i]);
            tmp+=str[start];
            recur(str,res,tmp,start+1);  
            tmp.pop_back();   
        }
    }  
};

发表于 2017-05-15 21:56:30 回复(5)
public ArrayList<String> Permutation(String str) {
		ArrayList<String> result = new ArrayList<String>();
		if (str == null || str.length() > 9 || str.length()==0) {
			return result;
		}
		str = str.trim();
		Permutation(str.toCharArray(), 0, result);
//		HashSet<String> hs = new HashSet<String>(result);  //此仅去重,没有字典序排列,可能错误
//		new ArrayList<String>(hs);
		Collections.sort(result);  //字典序排列  有些oj要求
		return result;

	}

	public static void Permutation(char[] data, int beginIdx,ArrayList<String> result) {
		if (beginIdx == data.length) {
			result.add(new String(data));
		} else {
			for (int i = beginIdx; i < data.length; ++i) {
				//有重复字符时,跳过
				if(i!=beginIdx && data[i]==data[beginIdx]) continue; 
				//当i==begin时,也要遍历其后面的所有字符;
                //当i!=begin时,先交换,使第begin位取到不同的可能字符,再遍历后面的字符
				char temp = data[beginIdx];
				data[beginIdx] = data[i];
				data[i] = temp;
				
				Permutation(data, beginIdx + 1, result);
				
				//为了防止重复的情况,还需要将begin处的元素重新换回来           恢复打扫战场,恢复为原来子串, data共享
				temp = data[beginIdx];
				data[beginIdx] = data[i];
				data[i] = temp;
				
				/* 举例来说“b(acd)” acd排列 ,为什么使用了两次swap函数?    函数栈变化恢复 ,  "acd第一次输出 cda后,完全退栈 返回data应该还是acd"
				                             交换栈                       退栈
				        bacd       bacd
				        bcad       bcad
				        bcda 打印  -> bcda
                */
			}
		}
	}

编辑于 2015-11-18 16:51:40 回复(5)

递归法和回溯法的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)
class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> out;
		int len = str.length();
		if(len == 0)
			return out;
		char* p = (char *)malloc((len+1)*sizeof(char));
		str.copy(p,len,0);

		//全排列,迭代
		myPermutation(p,0,len,out);
        //字典序排序
		sort(out.begin(),out.end());
        //去除重复项
        for(auto it = out.begin()+1;it!=out.end();){
            if(*it == *(it-1))
                it = out.erase(it);
            else
                it++;
        }
		return out;
    }
    
	void myPermutation(char* p,int k,int m,vector<string>& out){
		if(k == m){
			//将结果存入out中
			string s;
			for(int i = 0;i<m;++i)
				s+=p[i];
			out.push_back(s);
			return ;
		}
		for(int i = k;i<m;++i){
			swap(p[k],p[i]);
			myPermutation(p,k+1,m,out);
			swap(p[k],p[i]);          
		}    
	}
};

发表于 2017-02-06 14:50:42 回复(1)

全排列算法:从第一个元素开始,对每个元素,分别与它后面不相同的数交换

class Solution {
public:
    vector Permutation(string str) {
        vector res;
        int n = str.length();
        helper(str, res, 0, n-1);
        sort(res.begin(),res.end());
        return res;
    }
    void helper(string &str, vector &res, int begin, int end){
        if(begin == end){
            res.emplace_back(str);
            return ;
        }
        for(int i = begin; i <= end; ++i){
            if(!has_duplicate(str, begin, i)){
                if(str[begin] != str[i]){
                    swap(str[begin], str[i]);
                }
                helper(str, res, begin + 1, end);
                if(str[begin] != str[i]){
                    swap(str[begin], str[i]);
                }
            }
        }
    }
    // begin~k-1有没有重复元素
    bool has_duplicate(string &str, int begin, int k){
        for (int i = begin; i < k; ++i) {
            if(str[i] == str[k]){
                return true;
            }
        }
        return false;
    }
};

另一种解法,dfs

vector<string> Permutation_dfs(string str) {
        vector<string> res;
        int n = str.length();
        if(n == 0){
            return res;
        }
        sort(str.begin(), str.end());
        vector<bool> visited(n, false);
        string res_str = "";
        dfs_helper(res, str, res_str, visited);
        return res;
    }

    void dfs_helper(vector<string> &res, string &str, string &res_str, vector<bool> &visited){
        if(res_str.length() == str.length()){
            res.push_back(res_str);
            return ;
        }
        for(int i = 0; i < str.length(); ++i){
            if(visited[i]){
                continue;
            }
            if(i != 0 && !visited[i - 1] && str[i] == str[i - 1]){
                continue;
            }
            visited[i] = true;
            res_str.push_back(str[i]);
            dfs_helper(res, str, res_str, visited);
            res_str.pop_back();
            visited[i] = false;
        }
    }
编辑于 2019-04-11 22:30:24 回复(3)
class Solution:
    def Permutation(self, ss):
        if len(ss)==0:
            return []
        if len(ss)==1:
            return [ss]
        res=set()
        for i in range(len(ss)):
            for j in self.Permutation(ss[:i]+ss[i+1:]):
                res.add(ss[i]+j)
        return sorted(list(res))
发表于 2018-05-25 10:00:43 回复(0)
算法思路:
1)n个元素的全排列=(n-1个元素的全排列)+(另一个元素作为前缀)
2)出口:如果只有一个元素的全排列,则说明已经排完,则输出数组;
3)不断将每个元素放左第一个元素,然后将它作为前缀,并将其余元素继续全排列

public ArrayList<String>Permutation(String str){
   ArrayList<String>result=new ArrayList<>();
   if(null==str||str.length()<1){
     return result;
   }
   char[]charArray=str.toCharArray();
   HashSet<String>mediateResult=new HashSet<>();
   fullPerm(mediateResult,charArray,0,charArray.length-1);
   result.addAll(mediateResult);
   Collections.sort(result);
   return result;
}

private void fullPerm(HashSet<String>intermediateResult,char[]charArray,int start,int end){
   if(start==end){
     StringBuilder sb=new StringBuilder();
     for(char c:charArray){
       sb.append(c);
     }
     interMediateResult.add(sb.toString());
     return;
   }else{
     for(int i=start;i<=end;++i){
        swap(charArray,start,i);
        fullPerm(interMediateResult,charArray,start+1,end);
        swap(charArray,start,i);
     }
 }
} 


发表于 2017-01-04 10:14:29 回复(1)
我自己先写了一个标准的解法:通过交换遍历第k位可能的所有字符
     void PermutationHelp(vector<string> &ans, int k, string str) //遍历第k位的所有可能
	{
		if(k == str.size() - 1)
			ans.push_back(str);
		unordered_set<char> us;  //记录出现过的字符
		sort(str.begin() + k, str.end());  //保证按字典序输出
		for(int i = k; i < str.size(); i++)
		{
			if(us.find(str[i]) == us.end()) //只和没交换过的换
			{	
				us.insert(str[i]);
				swap(str[i], str[k]);
				PermutationHelp(ans, k + 1, str);
				swap(str[i], str[k]);  //复位
			}
		}
	}

    vector<string> Permutation(string str) {
		vector<string> ans;
		PermutationHelp(ans, 0, str);
		return ans;
    }

然后,我随意的尝试调整了一下代码, 把递归中的复位的swap去掉,排序去掉,改为最开始一次性排序。居然也通过了。可是我没理清楚为什么?
void PermutationHelp(vector<string> &ans, int k, string str) //遍历第k位的所有可能
	{
		if(k == str.size() - 1)
			ans.push_back(str);
		for(int i = k; i < str.size(); i++)
		{
			if(i != k && str[k] == str[i])
				continue;
			swap(str[i], str[k]);
			PermutationHelp(ans, k + 1, str);
		}
	}

	vector<string> Permutation(string str) {
		sort(str.begin(), str.end());
		vector<string> ans;
		PermutationHelp(ans, 0, str);
		return ans;
    }

编辑于 2018-12-26 14:11:30 回复(49)
class Solution {
public:
	set<string> res;
	void fun(string str, int pos)
	{
		if (pos == str.length())
		{
			res.insert(str);
			return;
		}
		for (int i = pos; i < str.length(); ++i)
		{
			swap(str[i], str[pos]);
			fun(str, pos + 1);
			swap(str[i], str[pos]);
		}
	}
	vector<string> Permutation(string str) {
		res.clear();
		vector<string> st;
		if (str.length() == 0)return st;
		fun(str, 0);
		set<string>::iterator it;
		for (it = res.begin(); it != res.end(); ++it)
			st.push_back(*it);
		return st;
	}
};

发表于 2016-08-01 15:22:53 回复(5)
分为两步:
  1. 求所有可能在第一个位置的字符,即把第一个字符和后面的依次交换
  2. 固定第一个字符,求后面所有字符的排列。后面所有的字符又可看成第一个字符跟后面所有的字符的排列。典型的递归思路
# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        if not ss:
            return []
        
        def Permutation(startIdx):
            if startIdx >= len(arrSs):
                clone = ''.join(arrSs)
                res.append(clone)
            else:
                changeIdx = startIdx
                while changeIdx < len(arrSs):
                    arrSs[changeIdx], arrSs[startIdx] = arrSs[startIdx], arrSs[changeIdx]
                    Permutation(startIdx + 1)
                    arrSs[changeIdx], arrSs[startIdx] = arrSs[startIdx], arrSs[changeIdx]
                    changeIdx += 1
        
        res = []
        arrSs = list(ss)
        Permutation(0)
        res = list(set(res))
        return sorted(res)

发表于 2016-07-26 09:22:04 回复(0)

基于回溯法思想:

图片说明

Java代码:

import java.util.List;
import java.util.Collections;
import java.util.ArrayList;

public class Solution {
    public static void main(String[] args) {
        Solution p = new Solution();
        System.out.println(p.Permutation("abc").toString());
    }

    public ArrayList<String> Permutation(String str) {
        List<String> res = new ArrayList<>();
        if (str != null && str.length() > 0) {
            PermutationHelper(str.toCharArray(), 0, res);
            Collections.sort(res);
        }
        return (ArrayList)res;
    }

    public void PermutationHelper(char[] cs, int i, List<String> list) {
        if (i == cs.length - 1) {
            String val = String.valueOf(cs);
            if (!list.contains(val)) 
                list.add(val);
        } else {
            for (int j = i; j < cs.length; j++) {
                swap(cs, i, j);
                PermutationHelper(cs, i+1, list);
                swap(cs, i, j);
            }
        }
    }

    public void swap(char[] cs, int i, int j) {
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
}
编辑于 2018-03-20 19:17:11 回复(55)
//利用STL中的next_permutation全排列函数
//next_permutation函数会取得[first,last)所标示序列的下一个排列组合,
//如果没有下一个排列组合返回false,有则返回true
class Solution {
public:
    vector<string> Permutation(string str) {
    	vector<string> ret;
        if(str.empty())
            return ret;
        sort(str.begin(),str.end());
        ret.push_back(str);
        while(next_permutation(str.begin(),str.end()))
            ret.push_back(str);
        return ret;
    }
};
//TODO:具体实现,递归和非递归2种方法
编辑于 2016-07-19 22:41:19 回复(0)
求助,JAVA怎么这样都能超时呢?  
 “qwertyuio”  运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。
代码如下:
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        // write code here
        ArrayList<String> result = new ArrayList<String>();
        char[] array = str.toCharArray();
        Arrays.sort(array);
        do {
            result.add(new String(array));
        } while(nextPermutation(array));
        return result;
    }
    
    public boolean nextPermutation(char[] array) {
        // 找较小值
        int len = array.length;
        int i = len-2;
        while(i>=0 && array[i]>=array[i+1]) i--;
        if(i<0) return false;
        // 找较大值
        int j = len-1;
        while(j>=0 && array[j]<=array[i]) j--;
        // 交换较小和较大值
        swap(array, i, j);
        // 反转升序区
        reverse(array, i+1);
        return true;
    }
    
    public void swap(char[] array, int i, int j) {
        if(i!=j) {
            char temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    
    public void reverse(char[] array, int start) {
        int left = start;
        int right = array.length-1;
        while(left<right) {
            swap(array, left, right);
            left++;
            right--;
        }
    }
}

发表于 2022-08-01 14:42:01 回复(0)
 class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res;//定义一个字符串数组,用来保存所有排列的字符串
        if(str.size()==0)//字符串为空
            return res;
        Permutation(res,str,0);//调用字符串排列函数
        sort(res.begin(),res.end());//对res字符串数组进行升序排列,不然测试不通过
        return res;//返回
    }
    void Permutation(vector<string> &res,string str,int begin){
        if(begin==str.size()-1)//遍历到字符串结尾,将其中一个字符串压入数组
            res.push_back(str);
        for(int i=begin;i<str.size();++i){//i从begin开始,依次交换
            if(i!=begin&&str[i]==str[begin])//当遇到重复字符,跳过
                continue;
            swap(str[i],str[begin]);//依次交换
            Permutation(res,str,begin+1);//对上一个交换结果的下一个字符依次交换
            swap(str[i],str[begin]);//begin交换回来,与下一个i交换
        }
        
    }
};

编辑于 2019-03-25 08:40:36 回复(0)
function Permutation(str)
{
    if(str.length==0) return []
    var array = [str[0]]
    for(let j = 1;j<str.length;j++){
        array = f(array,str[j])
    }
    return [...new Set(array)].sort()
    /* 
     * 下面的 f 函数是向字符串数组 a 中插入一个新字符,返回新的全排列数组, 
     * 例如向['aa']插入'b'得到['baa','aba','aab'] 
    */
    function f(a,ch){
        var o = []
        for(let i=0;i<=a[0].length;i++){
            o = o.concat(a.map(x=>x.slice(0,i)+ch+x.slice(i)))
        }
        return [...new Set(o)]
    }
}
发表于 2019-02-12 00:34:00 回复(0)
//对比了赞最多的那个方法,思路一样,但是用hashSet解决重复值问题效率更好
public class Solution{     private HashSet<String> set =new HashSet<>();     public ArrayList<String> Permutation(String str) {         ArrayList<String> list = new ArrayList<>();         if (str != null && str.length() > 0) {             permutation(str, 0);             list.addAll(set);             Collections.sort(list);         }         return list;
    }          private void permutation(String str, int start) {         char[] arr = str.toCharArray();         String r = null;         if (start == str.length()-1) {             r = String.valueOf(arr);             set.add(r);         } else {             for (int i = start; i < str.length(); i++) {                 char temp = arr[i];                 arr[i] = arr[start];                 arr[start] = temp;                 permutation(String.valueOf(arr), start+1);                 temp = arr[i];                 arr[i] = arr[start];                 arr[start] = temp;             }         }     }
}

发表于 2018-08-28 14:41:17 回复(0)