27字符串的排列

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

1)n个元素的全排列=(n-1个元素的全排列)+(另一个元素作为前缀)

2)出口:如果只有一个元素的全排列,则说明已经排完,则输出数组;

3)不断将每个元素放左第一个元素,然后将它作为前缀,并将其余元素继续全排列



abcd 将bcd 看成 m ->am 其中m 可以看成是 bm cm dm 
同理： 将acd 看成 m  ->bm

所以：
abcd 全排列就是am bm cm dm
对M 递归的算出全排列

 1 import java.util.ArrayList;
 2 import java.lang.StringBuffer;
 3 import java.util.concurrent.ConcurrentSkipListSet;
 4 import java.util.Set;
 5 public class Solution {
 6     private Set<String> result = new ConcurrentSkipListSet<String>();
 7     public ArrayList<String> Permutation(String str) {
 8           if(str.length() == 0){
 9             ArrayList<String> empty = new ArrayList<String>();
10             return empty;
11         }
12         char[] charArray = str.toCharArray();
13         fullperm(charArray, 0);
14         ArrayList<String> res = new ArrayList<String>(result);
15         return res;        
16     }
17     private void swap(char[] charArray,int start,int i){
18            char tmp = charArray[i];
19                 charArray[i] = charArray[start];
20                 charArray[start] = tmp;
21     }
22     private void fullperm(char[] charArray,int start ){
23         if(start==charArray.length-1){
24             StringBuffer sb = new StringBuffer();
25             for(char c  : charArray)
26                 sb.append(c);
27             result.add(sb.toString());
28             return;
29         }
30         for(int i=start;i<charArray.length;i++){                
31             swap(charArray,start, i);   
32             fullperm(charArray,start+1);
33             swap(charArray,start, i);
34         }
35     }
36 }

20180310

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

    def __init__(self):
        self.res = []

    def Permutation(self, ss):
        # write code here
        def swap(a,i,j):
            temp = a[i]
            a[i] = a[j]
            a[j] = temp
            
        def help(a,lo,hi):
            if(lo==hi):
                self.res.append(''.join(a))
            for i in range(lo,hi):
                if a[i] not in a[lo:i]:
                    swap(a,i,lo)
                    help(a,lo+1,hi)
                    swap(a,i,lo)
        if ss=='':
            return []
        ss = list(ss)
        help(ss,0,len(ss))
        return sorted(self.res)