【剑指offer】面试题38：字符串的排列

àì夳堔傛蜴生んèń 2022-06-11 03:07 188阅读 0赞

## 题目 ##

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。  
ps：输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

## 思路 ##

其实就是对字符串全排列，然后放到 TreeSet 中。  
放到TreeSet中解决了两个问题：1.去掉重复字符串，2.按字典序排序

这里讲一下全排列：  
1.字符串 “a” 的全排列就是自身  
2.字符串 “ab” 的全排列是 “ab”, “ba”  
3.字符串 “abc” 的全排列是 “abc”, “acb”, “bac”, “bca”, “cab”, “cba”，即：  
　第一个字符为a，加上 “bc” 的全排列；  
　第一个字符为b，加上 “ac” 的全排列；  
　第一个字符为c，加上 “ab” 的全排列。

即字符串的全排列，等于所有可能的首字符，加上剩下的字符的全排列的组合。  
然后再去求解剩下的字符的全排列，这个就变成了子问题。所以用递归求解。

## 代码 ##

/**
     * 题目：
     * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
     * 例如输入字符串abc, 则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
     * ps：输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
     * 
     * @author peige
     */
    public class _38_StringPermutation {
        
    
        TreeSet<String> set;
    
        public ArrayList<String> Permutation(String str) {
            if(str == null || str.trim().length() == 0)
                return new ArrayList<>();
            char[] chars = str.toCharArray();
            set = new TreeSet<>();
            Permutation(chars, 0);
            return new ArrayList<>(set);
        }
    
        private void Permutation(char[] chars, int index) {
            if(index == chars.length - 1) {
                set.add(new String(chars));
                return;
            }
            for(int i = index; i < chars.length; ++i) {
                swap(chars, i, index);
                Permutation(chars, index + 1);
                swap(chars, i, index);
            }
        }
    
        private void swap(char[] chars, int indexA, int indexB) {
            char c = chars[indexA];
            chars[indexA] = chars[indexB];
            chars[indexB] = c;
        }
    }

## 思路 ##

public class _38_Test {
        
    
        public static void main(String[] args) {
            test1();
            test2();
            test3();
        }
    
        /**
         * 功能测试
         * 1.有重复字符
         * 2.无重复字符
         */
        private static void test1() {
            _38_StringPermutation sp = new _38_StringPermutation();
            System.out.println(sp.Permutation("abc"));
            System.out.println(sp.Permutation("aAb"));
            System.out.println(sp.Permutation("aabc"));
        }
    
        /**
         * 边界测试
         * 1.只有一个字符
         * 2.有多个重复字符
         */
        private static void test2() {
            _38_StringPermutation sp = new _38_StringPermutation();
            System.out.println(sp.Permutation("a"));
            System.out.println(sp.Permutation("aaa"));
            System.out.println(sp.Permutation("aabb"));
        }
    
        /**
         * 极端测试
         * 1.输入null
         * 2.输入的字符串内容为空
         */
        private static void test3() {
            _38_StringPermutation sp = new _38_StringPermutation();
            System.out.println(sp.Permutation(null));
            System.out.println(sp.Permutation(""));
        }
    }