字符串的排列

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;
    }
};

//参照剑指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();   
        }
    }  
};

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
                */
			}
		}
	}

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]);          
		}    
	}
};

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

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;
        }
    }

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);
     }
 }
} 

     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;
    }

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;
    }

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;
	}
};

基于回溯法思想：

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;
    }
}

//利用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;
    }
};

 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交换
        }
        
    }
};

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)]
    }
}

//对比了赞最多的那个方法,思路一样,但是用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;             }         }     }
}

	

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        if(len(ss) ==0):
            return []
        if(len(ss) == 1):
            return list(ss)
        result = []
        tmp = list(ss)
        keep = list(ss)
        for i in set(keep):
            tmp = list(ss)
            tmp.pop(tmp.index(i))
            ans = self.Permutation(tmp)
            ans = [i+j for j in ans]
            result.extend(ans)
        return sorted(result)

//1、应用递归，想法很简单，遍历整个字符串，固定每个字符，将除去该字符的子序列
//进行排列，并将结果合并到该字符之后
//2、检测的时候应该忽视了字典排序，感觉是只按照给定字符串的顺序检测的
import java.util.ArrayList;
public class Solution {
    public ArrayList Permutation(String str) {
        ArrayList list = new ArrayList();
        int l = str.length();
        if(l == 0 ) return list;
        if(l == 1){
            list.add(str);
        }else{
            for(int i=0;i<l;i++){
                for(String tmp : Permutation(str.substring(0,i)+str.substring(i+1,l))){
                    String temp = str.charAt(i)+tmp;
                    if(!list.contains(temp)){
                        list.add(temp);
                    }
                }
            }
        }
        //Collections.sort(list);
        return list;
    }
}

import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<String>();
        if(str==null||str.length()==0)
            return result;
        char[] c = str.toCharArray();
        Permutation(result, c, 0, c.length);
        Collections.sort(result);
        return result;
    }

    public void Permutation(ArrayList<String> list,char[] c, int star,int end){
    	if(star==end-1){
    		String result = new String(c);
    		if(!list.contains(result))
    			list.add(result);
    		return;
    	}
    	//交換
    	for(int i = star;i<end;i++){
    		if(i!=star&&c[star]==c[i])
    			continue;
    		char temp = c[star];
    		char temp2 = c[i];
    		c[star] = temp2;
    		c[i] = temp;
    		Permutation(list,c,star+1,end);
    		c[star] = temp;
    		c[i] = temp2;
    	}
    }
}