题目描述

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

输入描述:

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

思路 & 解答

使用回溯，通过交换字符实现，主要重复元素需要跳过。步骤：

• 将字符串分为两部分，首字符和剩下字符。
• 将首字符和其他的字符进行交换，并以剩下的元素组成的字符串进行递归全排列。
• 直到交换完最后一个元素的时候，结束。

代码如下：

import java.util.ArrayList;
import java.util.Comparator;

public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> results = new ArrayList<>();
        if (str != null && str.length() > 0) {
            char[] chars = str.toCharArray();
            process(chars, results, 0);
        }
        results.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        });
        return results;
    }

    private void process(char[] chars, ArrayList<String> results, int index) {
        if (index == chars.length - 1) {
            if (!results.contains(new String(chars))) {
                results.add(new String(chars));
                return;
            }
        } else {
            for (int j = index; j < chars.length; j++) {
                swap(chars, index, j);
                process(chars, results, index + 1);
                swap(chars, index, j);
            }
        }
    }

    // 交换
    private void swap(char[] str, int i, int j) {
        if (i != j) {
            char t = str[i];
            str[i] = str[j];
            str[j] = t;
        }
    }
}

C++ 代码实现如下：

class Solution {
public:
    void process(int index, string s, set<string> &ret) {
        if (index + 1 == s.length()) {
            ret.insert(s);
            return;
        }
        for (int i = index; i < s.length(); ++i) {
            swap(s[index], s[i]);
            process(index + 1, s, ret);
            swap(s[index], s[i]);
        }
    }

    vector<string> Permutation(string s) {
        if (s.empty()) return {};
        set<string> ret;
        process(0, s, ret);
        return vector<string>({ret.begin(), ret.end()});
    }
};

• 时间复杂度：O(n!),全排列，指数级复杂度
• 空间复杂度：O(1),没有使用额外的空间