【剑指offer】面试题：求字符串的所有组合

喜欢ヅ旅行 2022-06-11 03:25 106阅读 0赞

## 题目 ##

输入一个字符串，打印出该字符串中字符的所有组合。  
例如输入三个字符a, b, c，则它们的组合有 a, b, c, ab, ac, bc, abc。  
当交换字符串中的字符时，虽然能得到两个不同的排列，但却是同一个组合。比如 ab 和 ba 是不同的排列，但只算一个组合。

## 思路 ##

如果输入n个字符，则这n个字符能构成长度为1, 2, …, n的组合。  
求n个字符的长度为m（1≤m≤n）的组合的时候，  
**我们把这n个字符分成两个部分：第一个字符和其余的所有字符。**

如果组合里包含第一个字符，则下一步在剩余的n-1个字符里选择m-1个字符；  
如果组合里不包含第一个字符，则下一步在剩余的n-1个字符里选择m个字符。

可以用递归解决。

## 代码 ##

/**
     * 题目：
     * 输入一个字符串，求字符串中字符的所有组合
     * 例如输入字符串"abc"，则它们的组合有a, b, c, ab, ac, bc, abc
     * 当交换字符串中的两个字符时，虽然能得到两个不同的排列，但却是同一个组合。
     * 比如 ab 和 ba 是不同的排列，但只算一个组合。
     * 
     * @author peige
     */
    public class _997_StringCombination {
        
    
        private StringBuilder sb;
        private Set<String> result;
        private int index;
    
        public ArrayList<String> stringCombination(String str) {
            if(str == null || str.trim().length() == 0)
                return new ArrayList<>();
            char chars[] = str.toCharArray();
            sb = new StringBuilder();
            result = new TreeSet<>();
            index = 0;
            for(int i = 1; i <= str.length(); ++i) {
                stringCombination(chars, i);
            }
            return new ArrayList<>(result);
        }
    
        private void stringCombination(char[] chars, int length) {
            if(length == 0) {
                result.add(sb.toString());
                return;
            }
            if(chars.length - index < length) {
                return;
            }
            // 选择第一个，从剩下的中选择length-1个
            sb.append(chars[index]);
            ++index;
            stringCombination(chars, length - 1);
            sb.deleteCharAt(sb.length() - 1);
    
            // 不选择第一个，从剩下的中选择length个
            stringCombination(chars, length);
            --index;
        }
    
    }

## 测试 ##

public class _997_Test {
        
    
        public static void main(String[] args) {
            test1();
            test2();
            test3();
        }
    
        /**
         * 功能测试
         */
        private static void test1() {
            _997_StringCombination sc = new _997_StringCombination();
            System.out.println(sc.stringCombination("abc"));
            System.out.println(sc.stringCombination("abcd"));
            System.out.println(sc.stringCombination("aabb"));
        }
    
        /**
         * 边界测试
         */
        private static void test2() {
            _997_StringCombination sc = new _997_StringCombination();
            System.out.println(sc.stringCombination("a"));
            System.out.println(sc.stringCombination("aaa"));
        }
    
        /**
         * 极端测试
         */
        private static void test3() {
            _997_StringCombination sc = new _997_StringCombination();
            System.out.println(sc.stringCombination(""));
            System.out.println(sc.stringCombination(null));
        }
    
    }