劍指 Offer 專題：字符串全排列（九度 OJ 1369）去重與字典序實現

題目描述

輸入一個字符串，按字典序打印出該字符串中字符的所有排列。例如輸入 abc，則輸出 abc, acb, bac, bca, cab, cba。

輸入輸出

• 每個測試案例佔一行，字符串長度 ≤ 9，可能包含重複字符，僅含大小寫字母。
• 按字典序輸出所有不重複排列，每個排列佔一行。

樣例

輸入： abc BCA
輸出： abc acb bac bca cab cba ABC ACB BAC BCA CAB CBA

解題核心難點

1. 去重：字符串可能含重複字符，需避免生成重複排列。
2. 字典序：輸出必須嚴格遵循字典順序。

算法思路

採用遞歸回溯 + 剪枝 + 區間排序策略：

1. 先將字符數組按字典序排序（冒泡排序即可，數據量小）。
2. 遞歸函數 Permutation(arr, k, len) 固定前 k 位，對第 k 位嘗試交換 k..len-1 的每個字符。
   • 若 arr[k] == arr[i] 且 k != i，直接 continue 跳過（去重關鍵）。
   • 交換後，對 k+1..len-1 區間重新排序，保證後續遞歸進入時序列有序。
   • 遞歸返回後，再次排序恢復原序，以便下一次交換基於有序序列。
3. 當 k == len 時輸出當前排列。

完整代碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void bubbleSort(char *arr, int begin, int length);
void swap(char *a, char *b);
void Permutation(char *arr, int k, int length);

int main() {
    char arr[10];
    int length;
    while (gets(arr)) {
        length = strlen(arr);
        bubbleSort(arr, 0, length);
        Permutation(arr, 0, length);
    }
    return 0;
}

void Permutation(char *arr, int k, int length) {
    int i;
    if (k == length) {
        for (i = 0; i < length; i++) printf("%c", arr[i]);
        printf("\n");
    } else {
        for (i = k; i < length; i++) {
            if (k != i && arr[k] == arr[i]) continue;  // 去重
            swap(&arr[k], &arr[i]);
            bubbleSort(arr, k + 1, length);            // 保證後綴有序
            Permutation(arr, k + 1, length);
            bubbleSort(arr, k + 1, length);            // 回溯恢復
        }
    }
}

void swap(char *a, char *b) {
    char c = *b;
    *b = *a;
    *a = c;
}

void bubbleSort(char *arr, int begin, int length) {
    int i, j;
    for (i = begin; i < length; i++)
        for (j = i + 1; j < length; j++)
            if (arr[i] > arr[j])
                swap(&arr[i], &arr[j]);
}

關鍵點解析

為什麼要「交換 → 排序 → 遞歸 → 排序」？

以 cba 為例：交換首尾得到 abc 後，若不排序直接遞歸，後綴 bc 可能無序，導致輸出順序錯誤。每次交換後對剩餘區間排序，確保進入下一層遞歸時序列始終有序，從而保證全局字典序。

去重邏輯

if (k != i && arr[k] == arr[i]) continue; 表示：若待交換字符與當前位字符相同，且非同一位置，則跳過。因為數組已排序，相同字符相鄰，這能避免同一層遞歸中選擇相同字符導致重複排列。

複雜度

• 時間：O(n! × n)，n ≤ 9 完全可接受。
• 空間：O(n) 遞歸棧 + 原地操作。