一篇學會字符串的排列

作者：程序員千羽 2021-12-08 14:02:20

排列方案的生成：根據字符串排列的特點，考慮深度優先搜索所有排列方案。即通過字符交換,先固定第1位字符( n種情況)、再固定第2位字符(n-1種情況)、...、最后固定第n位字符(1種情況)。

本文轉載自微信公眾號「程序員千羽」，作者程序員千羽。轉載本文請聯系程序員千羽公眾號。

Leetcode : https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_30_permutation/Solution.java

字符串的排列

“題目描述：輸入一個字符串，打印出該字符串中字符的所有排列。你可以以任意順序返回這個字符串數組，但里面不能有重復元素。為了讓您更好地理解問題，以下面的二叉搜索樹為例：難度：中等示例:

輸入：s = "abc" 
 
輸出：["abc","acb","bac","bca","cab","cba"]

解題思路：

對于一個長度為 n 的字符串(假設字符互不重復)，其排列方案數共有：

重復排列方案與剪枝：當字符串存在重復字符時，排列方案中也存在重復的排列方案。為排除重復方案，需在固定某位字符時，保證“每種字符只在此位固定一次” ，即遇到重復字符時不交換，直接跳過。從DFS角度看，此操作稱為"剪枝” 。

遞歸解析：

終止條件：當 x = len(c) - 1 時，代表所有位已固定(最后一位只有 11 種情況)，則將當前組合 c 轉化為字符串并加入 res ，并返回;
遞推參數：當前固定位 x ;
遞推工作：初始化一個 Set ，用于排除重復的字符;將第 x 位字符與 i ∈ [x, len(c)] 字符分別交換，并進入下層遞歸;
- 剪枝：若 c[i] 在 Set 中，代表其是重復字符，因此 “剪枝” ;
- 將 c[i] 加入 Set ，以便之后遇到重復字符時剪枝;
- 固定字符：將字符 c[i] 和 c[x] 交換，即固定 c[i] 為當前位字符;
- 開啟下層遞歸：調用 dfs(x + 1) ，即開始固定第 x + 1 個字符;
- 還原交換：將字符 c[i] 和 c[x] 交換(還原之前的交換);

下圖中 list 對應文中的列表 c 。比如

舉個例子：

通過交換來固定某個位置的元素這個思路， 
就 abc 這個字符串來說，第一個位置可以放 a 或者 b 或者 c，但是如果確定要放某個字符， 
比如第一個位置放 a，那么第二個位置就只能放 b 或者 c； 
如果第一個位置放 b，那么第二個位置就只能放 a 或者 c； 
如果第一個位置放 c，那么第二個位置就只能放 a 或者 b； 
當把某個字符移動到第一位以后，暫時第一位的字符就固定住了， 
這時再去確定第二個位置的元素，并且此時第一個位置的元素不會再出現在后面的位置上， 
依次類推直到確定所有位置的元素，再往前回溯確定每個位置上其他可能出現的元素。

復雜度分析:

時間復雜度0(N!N) ：N為字符串s的長度;時間復雜度和字符串排列的方案數成線性關系，案數為N x(N- 1)x (N- 2)...x2x1，即復雜度為0(N!) ;

字符串拼接操作join() 使用O(N)因此總體時間復雜度為O(N!N)。

空間復雜度0(N2) ：全排列的遞歸深度為N，系統累計使用棧空間大小為0(N) ;

遞歸中輔助Set累計存儲的字符數量最多為N +(N- 1)+...+2+1=(N + 1)N/2 ,即占用O(N2)的額外空間。

package com.nateshao.sword_offer.topic_30_permutation; 
 
import java.util.ArrayList; 
import java.util.Collections; 
import java.util.HashSet; 
import java.util.List; 
 
/** 
 * @date Created by 邵桐杰 on 2021/12/2 15:31 
 * @微信公眾號 程序員千羽 
 * @個人網站 www.nateshao.cn 
 * @博客 https://nateshao.gitee.io 
 * @GitHub https://github.com/nateshao 
 * @Gitee https://gitee.com/nateshao 
 * Description: 劍指 Offer 38. 字符串的排列 
 */ 
public class Solution { 
 
    public static void main(String[] args) { 
        String str = "abc"; 
        ArrayList<String> list = permutation2(str); 
        list.stream().forEach(lists-> System.out.print( lists+" " )); // abc acb bac bca cab cba 
        System.out.println(); 
        for (String s : list) { 
            System.out.print(s + " "); // abc acb bac bca cab cba 
        } 
    } 
     
    /** 
     * 劍指offer 
     * 解題思路：將當前位置的字符和前一個字符位置交換，遞歸. 
     * @param str 
     * @return 
     */ 
    public static ArrayList<String> permutation2(String str) { 
        ArrayList<String> res = new ArrayList<>(); 
        if (str == null) return res; 
        helper(res, 0, str.toCharArray()); 
        // 符合結果的輸出順序 
        Collections.sort(res); 
        return res; 
 
    } 
 
    private static void helper(ArrayList<String> res, int index, char[] s) { 
        if (index == s.length - 1) { 
            res.add(String.valueOf(s)); 
            return; 
        } 
        for (int i = index; i < s.length; i++) { 
            if (i == index || s[index] != s[i]) { 
                swap(s, index, i); 
                helper(res, index + 1, s); 
                swap(s, index, i); 
            } 
        } 
    } 
     
    public static void swap(char[] c, int a, int b) { 
        char temp = c[a]; 
        c[a] = c[b]; 
        c[b] = temp; 
    } 
    /********************** 精選解答 **************************/ 
    //為了讓遞歸函數添加結果方便，定義到函數之外，這樣無需帶到遞歸函數的參數列表中 
    List<String> list = new ArrayList<>(); 
    //同；但是其賦值依賴c，定義聲明分開 
    char[] c; 
    public String[] permutation(String s) { 
        c = s.toCharArray(); 
        //從第一層開始遞歸 
        dfs(0); 
        //將字符串數組ArrayList轉化為String類型數組 
        return list.toArray(new String[list.size()]); 
    } 
 
    public void dfs(int x) { 
        //當遞歸函數到達第三層，就返回，因為此時第二第三個位置已經發生了交換 
        if (x == c.length - 1) { 
            //將字符數組轉換為字符串 
            list.add(String.valueOf(c)); 
            return; 
        } 
        //為了防止同一層遞歸出現重復元素 
        HashSet<Character> set = new HashSet<>(); 
        //這里就很巧妙了,第一層可以是a,b,c那么就有三種情況，這里i = x,正巧dfs(0)，正好i = 0開始 
        // 當第二層只有兩種情況，dfs(1）i = 1開始 
        for (int i = x; i < c.length; i++){ 
            //發生剪枝，當包含這個元素的時候，直接跳過 
            if (set.contains(c[i])){ 
                continue; 
            } 
            set.add(c[i]); 
            //交換元素，這里很是巧妙，當在第二層dfs(1),x = 1,那么i = 1或者 2， 不是交換1和1，要就是交換1和2 
            swap(i,x); 
            //進入下一層遞歸 
            dfs(x + 1); 
            //返回時交換回來，這樣保證到達第1層的時候，一直都是abc。這里捋順一下，開始一直都是abc，那么第一位置總共就3個交換 
            //分別是a與a交換，這個就相當于 x = 0, i = 0; 
            //     a與b交換            x = 0, i = 1; 
            //     a與c交換            x = 0, i = 2; 
            //就相當于上圖中開始的三條路徑 
            //第一個元素固定后，每個引出兩條路徑, 
            //     b與b交換            x = 1, i = 1; 
            //     b與c交換            x = 1, i = 2; 
            //所以，結合上圖，在每條路徑上標注上i的值，就會非常容易好理解了 
            swap(i,x); 
        } 
    } 
    private void swap(int i, int x) { 
        char temp = c[i]; 
        c[i] = c[x]; 
        c[x] = temp; 
    } 
}

參考文章：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by

責任編輯：武曉燕來源：程序員千羽

符串排列搜索