【剑指offer】字符串的排列

1. 全排列的递归实现
全排列的递归实现就是从第一个数字起每个数分别与它后面的数字交换。

import java.util.ArrayList;

public class Solution {
    ArrayList<String> list = new ArrayList<>();

    public void Per(char[] str, int k) {
        if (k == str.length) {
            list.add(String.valueOf(str));
        } else {
            char tep;
            for (int i = k; i < str.length; i++) { // 第i个数分别与它后面的数字交换就能得到新的排列
                tep = str[i];
                str[i] = str[k];
                str[k] = tep;
                Per(str, k + 1);
                tep = str[i];
                str[i] = str[k];
                str[k] = tep;
            }
        }
    }

    public ArrayList<String> Permutation(String str) {
        if (str != null && str.length() != 0) {
            Per(str.toCharArray(), 0);
        }
        return list;
    }
}

2. 去重全排列的递归实现
去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换

import java.util.ArrayList;

public class Solution {
    ArrayList<String> list = new ArrayList<>();

    public boolean jude(char[] str, int st, int ed) { // 第i个数与第j个数交换时，要求[i,j)中没有与第j个数相等的数
        for (int i = st; i < ed; i++) {
            if (str[i] == str[ed]) {
                return false;
            }
        }
        return true;
    }

    public void Per(char[] str, int k) {
        if (k == str.length) {
            list.add(String.valueOf(str));
        } else {
            char tep;
            for (int i = k; i < str.length; i++) { // 第i个数分别与它后面的数字交换就能得到新的排列
                if (jude(str, k, i)) {
                    tep = str[i];
                    str[i] = str[k];
                    str[k] = tep;
                    Per(str, k + 1);
                    tep = str[i];
                    str[i] = str[k];
                    str[k] = tep;
                }
            }
        }
    }

    public ArrayList<String> Permutation(String str) {
        if (str != null && str.length() != 0) {
            Per(str.toCharArray(), 0);
        }
        return list;
    }
}

3. 去重字典序法实现
去重字典序法实现，引入标记数组vis，保证了字典序的顺序输出。

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    ArrayList<String> list = new ArrayList<>();
    boolean[] vis = new boolean[10]; // vis标记数组，表示第i个位置的数是否被用过
    char[] pri = new char[10];       // pri数组记录每个位置填的数

    public void Per(char[] str, int k) {
        if (k == str.length) {
            list.add(String.valueOf(pri, 0, str.length));
        } else {
            for (int i = 0; i < str.length; i++) { // 遍历寻找没被访问的数
                if (!vis[i]) {
                    vis[i] = true;
                    pri[k] = str[i];
                    Per(str, k + 1);
                    vis[i] = false;
                    while (i + 1 < str.length && str[i] == str[i + 1]) i++; // 对于一次输出在第i位置只放一次相同的数
                }
            }
        }
    }
    public ArrayList<String> Permutation(String str) {
        if (str != null && str.length() != 0) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            Per(chars, 0);
        }
        return list;
    }
}