leetcode字符串的全排列题解

红太狼 2023-10-04 16:24 10阅读 0赞

解法描述：

例如，如果集合是\{a,b,c\},那么这个集合中元素的所有排列是\{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)\}，显然，给定n个元素共有n!种不同的排列，如果给定集合是\{a,b,c,d\}，可以用下面给出的简单算法产生其所有排列，即集合(a,b,c,d)的所有排列有下面的排列组成：

（1）以a开头后面跟着(b,c,d)的排列
    
    （2）以b开头后面跟着(a,c,d)的排列
    
    （3）以c开头后面跟着(a,b,d)的排列
    
    （4）以d开头后面跟着(a,b,c)的排列，这显然是一种递归的思路

基于以上出来的是包含重复的排列，要去重需要换种思维，  
例如：对122，第一个数1与第二个数2交换得到212，然后考虑第一个数1与第三个数2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212，它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。  
这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。

class Solution {
        
        public String[] permutation(String s) {
        
    
            List<String> list = new ArrayList<String>();
    
            char[] array = s.toCharArray();
            // 第一个字符与后面非重复出现的交换
            int n = array.length;
            permutate(list, array, 0);
    
            return list.toArray(new String[list.size()]);
            
    
        }
        public void permutate(List<String> list, char[] data, int begin){
        
            int length = data.length;
            if(begin == length)
                list.add(String.valueOf(data));
            for(int i = begin ; i < length; i++)
            {
        
                if(isUnique(data, begin, i)){
        
                    swap(data, begin, i);
                    permutate(list, data, begin + 1);
                    swap(data, begin, i);
                }                
            }
        }
        
    
        // 判断后续是否存在重复字符
        public boolean isUnique(char[] array, int begin, int end) {
        
    
            for (int i = begin; i < end; i++) {
        
    
                if (array[i] == array[end])
                    return false;
            }
            return true;
    
        }
        // 交换两个字符
        public void swap(char[] array, int i, int j) {
        
            
            char temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

参考：https://blog.csdn.net/hackbuteer1/article/details/6657435  
https://blog.csdn.net/dengyinqing9059/article/details/102209681?utm\_medium=distribute.pc\_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-2.base&depth\_1-utm\_source=distribute.pc\_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-2.base