【剑指Offer】027——字符串的排列 （字符串）

题目描述

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

输入描述:

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

解题思路

刚看题目的时候，可能会觉得这个问题很复杂，不能一下子想出解决方案。那我们就要学会把复杂的问题分解成小问题。我们求整个字符串的排列，其实可以看成两步：

• 第一步求所有可能出现在第一个位置的字符（即把第一个字符和后面的所有字符交换[相同字符不交换]）；
• 第二步固定第一个字符，求后面所有字符的排列。这时候又可以把后面的所有字符拆成两部分（第一个字符以及剩下的所有字符），依此类推。这样，我们就可以用递归的方法来解决。

file

参考代码

Java

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> Permutation(String str) {
        if(str == null) return res;
        PermutationHelper(str.toCharArray(),0);
        Collections.sort(res);//对结果进行排序
        return res;      
    }
    public void PermutationHelper(char[] str, int i){
        if(i == str.length - 1){ // 到只有一个字符时
            res.add(String.valueOf(str)); 
        }else{
            for (int j = i; j < str.length; j++) {
                // 前后字符相同，不交换
                if(j!=i && str[i] == str[j]) continue;
                swap(str,i,j);
                PermutationHelper(str, i + 1); //固定第一个字符，对后面所有字符全排列
                swap(str,i,j); // 交换回来
            }
        }
    }
    public void swap(char[] str, int i, int j){
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
}

Python

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.res = []
    def Permutation(self, ss):
        # write code here
        if ss == None:
            return
        if len(ss) == 1:
            return [ss]
        self.PermutationHelper(ss, 0)
        return sorted(list(set(self.res)))
    def PermutationHelper(self, temp_ss, index):
        if index == len(temp_ss) - 1:
            self.res.append(temp_ss)
        else:
            for j in range(index, len(temp_ss)):
                if j!=index and temp_ss[j] == temp_ss[index]:continue
                temp_ss = list(temp_ss)  # 字符串不可直接修改
                temp_ss[j],temp_ss[index] = temp_ss[index], temp_ss[j]
                temp_ss = "".join(temp_ss)
                self.PermutationHelper(temp_ss, index + 1)
                temp_ss = list(temp_ss)
                temp_ss[j],temp_ss[index] = temp_ss[index], temp_ss[j]
                temp_ss = "".join(temp_ss)
                

个人订阅号

image