Java遞歸實現字元串的排列和組合
- 2019 年 11 月 22 日
- 筆記
我們在筆試中經常會遇到需要對字元串進行排列或者組合的題目。本篇文章對字元串的排列和組合進行遞歸版本的實現。
1. 字元串的組合
題目：輸入一個字元串，輸出該字元串中字元的所有組合。
例子：輸入：abc，它的組合有：a、b、c、ab、ac、bc、abc
分析：我們可以將字元串中的每個字元看成二叉樹的一個節點，根節點為空，每個節點都會有兩種選擇：要 和 不要 兩種選擇 。那麼我們就可以利用遞歸實現。
- 程式碼實現：
package com.offer.manongqiuzhi.String; /** * @author pcwl * @description：遞歸實現字元串的組合 */public class CombinationString { public static void printAllSubString(String str){ if(str == null){ return; } char[] chars = str.toCharArray(); if(chars.length > 0){ String pre = new String(""); // pre：用於表示從0到i-1位置上形成的結果 printAllSubString(0, pre, chars); }else{ System.out.println(""); // 輸入空字元串也會列印空 } } public static void printAllSubString(int i, String pre, char[] chars){ // 迭代終止條件 if(i == chars.length){ // 說明已經到最後一個字元了，所有的選擇都已經做完了，應該返回了 System.out.println(pre); return; } // 如果沒有到最後一個字元，那麼當前字元有兩種選擇：選擇要 和 選擇不要 printAllSubString(i + 1, pre, chars); // 不要當前字元 printAllSubString(i + 1, pre + String.valueOf(chars[i]), chars); // 要當前字元 } // 測試 public static void main(String[] args) { printAllSubString("abc"); }}
運行結果：
2. 字元串的排列
01
全排列
題目：輸入一個字元串，列印出該字元串中字元的所有排列。
舉例：輸入字元串 abc，則輸出由字元 a、b、c 所能排列出來的所有字元串 abc、acb、bac、bca、cab 和 cba。
分析：排列和上面的組合問題思想是一樣的：上面的組合問題，每個節點只有 「要」 和 「不要」 兩種選擇，而排列這裡每個節點 i 有 n – i 種選擇。
排列問題：所有的排列都是包含該字元串中所有的字元，所以不需要像組合那樣利用額外的空間 pre 記錄選擇的過程。
需要注意的是：i 位置在進行選擇的時候，會先和 i + 1 位置交換位置，搞定 i + 1 後面的排列後，會再和 i + 2 ~ n – 1 位置上的每個元素交換一次，所以為了保證都是和 i 位置上的元素進行交換，每次遞歸一次後，必須要將 i 位置元素再換回原來的位置。
可以直觀的理解下：加入現在搞定 i 位置上元素，i 一共有 n – i 種選擇，每次 i 位置固定後，i + 1 ~ n – 1 位置上的元素都是同樣遞歸實現。
- 程式碼實現：
package com.offer.manongqiuzhi.String; /** * @author pcwl * @description：遞歸實現全排列 */public class PermutationString { public static void printAllSort(String string){ if(string == null){ return; } char[] chars = string.toCharArray(); if(chars.length > 0){ printAllSort(0, chars); } } // 對i及i以後的字元進行全排列 public static void printAllSort(int i, char[] chars){ // 遞歸終止條件 if(i == chars.length){ System.out.println(String.valueOf(chars)); } for(int j = i; j < chars.length; j++){ swap(i, j, chars); // 第 i 個位置有 i ~ (n - 1) 種選擇。n 為字元串的長度 printAllSort(i + 1, chars); swap(i, j, chars); // 保證 i 後面的字元每次都是和 i 位置上的元素進行的交換，還需要將 i 和 j 交換回來 } } public static void swap(int i, int j, char[] chars){ int temp = chars[i]; chars[i] = chars[j]; chars[j] = chars[i]; } public static void main(String[] args) { printAllSort("abcc"); }}
運行結果：
02
去重全排列
只需要增加一個 hashset，用於保證重複字元不會被再次交換。
package com.offer.manongqiuzhi.String; import java.util.HashSet; /** * @author pcwl * @description：遞歸實現全排列（去重） */public class StringByRemoveDuplicate { public static void printAllSort(String string){ if(string == null){ return; } char[] chars = string.toCharArray(); if(chars.length > 0){ printAllSort(0, chars); } } // 對i及i以後的字元進行全排列 public static void printAllSort(int i, char[] chars){ // 遞歸終止條件 if(i == chars.length){ System.out.println(String.valueOf(chars)); } // 用於保證每次交換的字元不存在重複的字元 HashSet<Character> set = new HashSet<>(); for(int j = i; j < chars.length; j++){ if(!set.contains(chars[j])){ set.add(chars[j]); // 第 i 個位置有 i ~ (n - 1) 種選擇。n 為字元串的長度 swap(i, j, chars); printAllSort(i + 1, chars); // 保證 i 後面的字元每次都是和 i 位置上的元素進行的交換，還需要將 i 和 j 交換回來 swap(i, j, chars); } } } public static void swap(int i, int j, char[] chars){ int temp = chars[i]; chars[i] = chars[j]; chars[j] = chars[i]; } public static void main(String[] args) { printAllSort("abcc"); }}
運行結果：
——– END ———
