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; } }
import java.util.ArrayList; import java.util.List; import java.util.Collections; public class Solution { public ArrayList<String> Permutation(String str) { List<String> resultList = new ArrayList<>(); if(str.length() == 0) return (ArrayList)resultList; //递归的初始值为(str数组,空的list,初始下标0) fun(str.toCharArray(),resultList,0); Collections.sort(resultList); return (ArrayList)resultList; } private void fun(char[] ch,List<String> list,int i){ //这是递归的终止条件,就是i下标已经移到char数组的末尾的时候,考虑添加这一组字符串进入结果集中 if(i == ch.length-1){ //判断一下是否重复 if(!list.contains(new String(ch))){ list.add(new String(ch)); return; } }else{ //这一段就是回溯法,这里以"abc"为例 //递归的思想与栈的入栈和出栈是一样的,某一个状态遇到return结束了之后,会回到被调用的地方继续执行 //1.第一次进到这里是ch=['a','b','c'],list=[],i=0,我称为 状态A ,即初始状态 //那么j=0,swap(ch,0,0),就是['a','b','c'],进入递归,自己调自己,只是i为1,交换(0,0)位置之后的状态我称为 状态B //i不等于2,来到这里,j=1,执行第一个swap(ch,1,1),这个状态我称为 状态C1 ,再进入fun函数,此时标记为T1,i为2,那么这时就进入上一个if,将"abc"放进list中 /////////////-------》此时结果集为["abc"] //2.执行完list.add之后,遇到return,回退到T1处,接下来执行第二个swap(ch,1,1),状态C1又恢复为状态B //恢复完之后,继续执行for循环,此时j=2,那么swap(ch,1,2),得到"acb",这个状态我称为C2,然后执行fun,此时标记为T2,发现i+1=2,所以也被添加进结果集,此时return回退到T2处往下执行 /////////////-------》此时结果集为["abc","acb"] //然后执行第二个swap(ch,1,2),状态C2回归状态B,然后状态B的for循环退出回到状态A // a|b|c(状态A) // | // |swap(0,0) // | // a|b|c(状态B) // / \ // swap(1,1)/ \swap(1,2) (状态C1和状态C2) // / \ // a|b|c a|c|b //3.回到状态A之后,继续for循环,j=1,即swap(ch,0,1),即"bac",这个状态可以再次叫做状态A,下面的步骤同上 /////////////-------》此时结果集为["abc","acb","bac","bca"] // a|b|c(状态A) // | // |swap(0,1) // | // b|a|c(状态B) // / \ // swap(1,1)/ \swap(1,2) (状态C1和状态C2) // / \ // b|a|c b|c|a //4.再继续for循环,j=2,即swap(ch,0,2),即"cab",这个状态可以再次叫做状态A,下面的步骤同上 /////////////-------》此时结果集为["abc","acb","bac","bca","cab","cba"] // a|b|c(状态A) // | // |swap(0,2) // | // c|b|a(状态B) // / \ // swap(1,1)/ \swap(1,2) (状态C1和状态C2) // / \ // c|b|a c|a|b //5.最后退出for循环,结束。 for(int j=i;j<ch.length;j++){ swap(ch,i,j); fun(ch,list,i+1); swap(ch,i,j); } } } //交换数组的两个下标的元素 private void swap(char[] str, int i, int j) { if (i != j) { char t = str[i]; str[i] = str[j]; str[j] = t; } } }
class Solution { public: vector<string> Permutation(string str) { vector<string> result; if(str.empty()) return result; Permutation(str,result,0); // 此时得到的result中排列并不是字典顺序,可以单独再排下序 sort(result.begin(),result.end()); return result; } void Permutation(string str,vector<string> &result,int begin) { if(begin == str.size()-1) // 递归结束条件:索引已经指向str最后一个元素时 { if(find(result.begin(),result.end(),str) == result.end()) { // 如果result中不存在str,才添加;避免aa和aa重复添加的情况 result.push_back(str); } } else { // 第一次循环i与begin相等,相当于第一个位置自身交换,关键在于之后的循环, // 之后i != begin,则会交换两个不同位置上的字符,直到begin==str.size()-1,进行输出; for(int i=begin;i<str.size();++i) { swap(str[i],str[begin]); Permutation(str,result,begin+1); swap(str[i],str[begin]); // 复位,用以恢复之前字符串顺序,达到第一位依次跟其他位交换的目的 } } } void swap(char &fir,char &sec) { char temp = fir; fir = sec; sec = temp; } };
# -*- coding:utf-8 -*- class Solution: def Permutation(self, ss): if len(ss) <= 1: return ss res = set() # 遍历字符串,固定第一个元素,第一个元素可以取a,b,c...,然后递归求解 for i in range(len(ss)): for j in self.Permutation(ss[:i] + ss[i+1:]): # 依次固定了元素,其他的全排列(递归求解) res.add(ss[i] + j) # 集合添加元素的方法add(),集合添加去重(若存在重复字符,排列后会存在相同,如baa,baa) return sorted(res) # sorted()能对可迭代对象进行排序,结果返回一个新的list
public ArrayList<String> Permutation(String str) { ArrayList<String> res = new ArrayList<>(); if (str != null && str.length() > 0) { char[] seq = str.toCharArray(); Arrays.sort(seq); //排列 res.add(String.valueOf(seq)); //先输出一个解 int len = seq.length; while (true) { int p = len - 1, q; //从后向前找一个seq[p - 1] < seq[p] while (p >= 1 && seq[p - 1] >= seq[p]) --p; if (p == 0) break; //已经是“最小”的排列,退出 //从p向后找最后一个比seq[p]大的数 q = p; --p; while (q < len && seq[q] > seq[p]) q++; --q; //交换这两个位置上的值 swap(seq, q, p); //将p之后的序列倒序排列 reverse(seq, p + 1); res.add(String.valueOf(seq)); } } return res; } public static void reverse(char[] seq, int start) { int len; if(seq == null || (len = seq.length) <= start) return; for (int i = 0; i < ((len - start) >> 1); i++) { int p = start + i, q = len - 1 - i; if (p != q) swap(seq, p, q); } } public static void swap(char[] cs, int i, int j) { char temp = cs[i]; cs[i] = cs[j]; cs[j] = temp; }
public ArrayList<String> Permutation(String str) { ArrayList<String> res = new ArrayList<>(); if (str != null && str.length() > 0) { PermutationHelper(str.toCharArray(), 0, res); Collections.sort(res); } return res; } private static void PermutationHelper(char[] cs, int i, ArrayList<String> list) { if(i == cs.length - 1) { //解空间的一个叶节点 list.add(String.valueOf(cs)); //找到一个解 } else { for(int j = i; j < cs.length; ++j) { if(j == i || cs[j] != cs[i]) { SwapUtil.swap(cs, i, j); PermutationHelper(cs, i + 1, list); SwapUtil.swap(cs, i, j); //复位 } } } }
import java.util.*; public class Solution { public ArrayList<String> Permutation(String str) { ArrayList<String> re = new ArrayList<String>(); if (str == null || str.length() == 0) { return re; } HashSet<String> set = new HashSet<String>(); fun(set, str.toCharArray(), 0); re.addAll(set); Collections.sort(re); return re; } void fun(HashSet<String> re, char[] str, int k) { if (k == str.length) { re.add(new String(str)); return; } for (int i = k; i < str.length; i++) { swap(str, i, k); fun(re, str, k + 1); swap(str, i, k); } } void swap(char[] str, int i, int j) { if (i != j) { char t = str[i]; str[i] = str[j]; str[j] = t; } } }
class Solution { public: vector<string> Permutation(string str) { if(str.empty()) return ans; chang(str, 0, str.size()); sort(ans.begin(),ans.end()); auto it = unique(ans.begin(),ans.end()); ans.erase(it,ans.end()); return ans; } void chang(string &str,int start,int len){ if(start == len) ans.push_back(str); // for(int i = start; i < len; i++){ swap(str[start],str[i]); chang(str, start+1,len); swap(str[start],str[i]); } } vector<string> ans; };
class Solution { public: vector<string> Permutation(string str) { //可以用递归来做 vector<string> array; if(str.size()==0) return array; Permutation(array, str, 0); sort(array.begin(), array.end()); return array; } void Permutation(vector<string> &array, string str, int begin)//遍历第begin位的所有可能性 { if(begin==str.size()-1) array.push_back(str); for(int i=begin; i<=str.size()-1;i++) { if(i!=begin && str[i]==str[begin])//有重复字符时,跳过 continue; swap(str[i], str[begin]);//当i==begin时,也要遍历其后面的所有字符; //当i!=begin时,先交换,使第begin位取到不同的可能字符,再遍历后面的字符 Permutation(array, str, begin+1);//遍历其后面的所有字符; swap(str[i], str[begin]);//为了防止重复的情况,还需要将begin处的元素重新换回来 /*举例来说“abca”,为什么使用了两次swap函数 交换时是a与b交换,遍历; 交换时是a与c交换,遍历;(使用一次swap时,是b与c交换) 交换时是a与a不交换; */ } } };
用DFS做得,顺便练习下,嘿嘿 import java.util.*; public class Solution { private char [] seqs; private Integer [] book; //用于结果去重 private HashSet<String> result = new HashSet<String>(); /** * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。 * 例如输入字符串abc,则打印出由字符a,b,c * 所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。\ * @param str * @return */ public ArrayList<String> Permutation(String str) { ArrayList<String> arrange = new ArrayList<String>(); if(str == null || str.isEmpty()) return arrange; char[] strs = str.toCharArray(); seqs = new char[strs.length]; book = new Integer[strs.length]; for (int i = 0; i < book.length; i++) { book[i] = 0; } dfs(strs, 0); arrange.addAll(result); Collections.sort(arrange); return arrange; } /** * 深度遍历法 */ private void dfs(char[] arrs, int step){ //走完所有可能 记录排列 if(arrs.length == step){ String str = ""; for (int i = 0; i < seqs.length; i++) { str += seqs[i]; } result.add(str); return; //返回上一步 } //遍历整个序列,尝试每一种可能 for (int i = 0; i < arrs.length; i++) { //是否走过 if(book[i] == 0){ seqs[step] = arrs[i]; book[i] = 1; //下一步 dfs(arrs, step + 1); //走完最后一步 后退一步 book[i] = 0; } } } }
function Permutation(str) { let res=[]; if(str.length<=0) return res; arr=str.split("");//将字符串转化为字符数组 res=permutate(arr,0,res); res=[...new Set(res)]; res.sort(); return res; } function permutate(arr,index,res){ if(arr.length==index){ let s=""; for(let i=0;i<arr.length;i++){ s+=arr[i]; } return res.push(s); }else{ for(var i=index;i<arr.length;i++){ [arr[index],arr[i]]=[arr[i],arr[index]]; permutate(arr,index+1,res); [arr[index],arr[i]]=[arr[i],arr[index]]; } } return res; }
function Permutation(str) { let res=[],pStr=""; if(str.length<=0) return res; arr=str.split("");//将字符串转化为字符数组 res=permutate(arr,pStr,res); return res; } function permutate(arr,pStr,res){ if(arr.length==0){ return res.push(pStr); }else{ let isRepeated=new Set(); for(let i=0;i<arr.length;i++){ if(!isRepeated.has(arr[i])){//避免相同的字符交换 let char=arr.splice(i,1)[0]; pStr+=char; permutate(arr,pStr,res); arr.splice(i,0,char);//恢复字符串,回溯 pStr=pStr.slice(0,pStr.length-1);//回溯 isRepeated.add(char); } } } return res; }
//比较简单的代码,这个题目算经典的 class Solution { public: vector<string> Permutation(string str) { if(str!="") dfs(str, 0); return ret; } private: vector<string> ret; void dfs(string str, int s){ int sz = str.size(); if(s==sz){ ret.push_back(str); return; } for(int i = s; i < sz; ++i){ if(i!=s && str[s]==str[i]) continue; swap(str[s], str[i]); dfs(str, s+1); } } };
利用栈来实现排序,真的是太巧妙了,分享给大家。 public class Solution { public ArrayList<String> Permutation(String str) { TreeSet<String> tree = new TreeSet<>(); Stack<String[]> stack = new Stack<>(); ArrayList<String> results = new ArrayList<>(); stack.push(new String[]{str,""}); do{ String[] popStrs = stack.pop(); String oldStr = popStrs[1]; String statckStr = popStrs[0]; for(int i =statckStr.length()-1;i>=0;i--){ String[] strs = new String[]{statckStr.substring(0,i)+statckStr.substring(i+1),oldStr+statckStr.substring(i,i+1)}; if(strs[0].length()==0){ tree.add(strs[1]); }else{ stack.push(strs); } } }while(!stack.isEmpty()); for(String s : tree) results.add(s); return results; } }
# -*- coding:utf-8 -*-
import itertools
class Solution:
def Permutation(self, ss):
# write code here
result=[]
if not ss:
return []
else:
res=itertools.permutations(ss)
for i in res:
if "".join(i) not in result:
result.append("".join(i))
return result
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 */ } } }