Java 字符串鏡像遞歸算法：輸入字符串與逆轉次數，輸出鏡像拼接結果完整實現

題目需求解析

輸入：一個字符串 `str` 和一個整數 `num` (逆轉次數)。
操作：執行 `num` 次「鏡像逆轉拼接」：
    每次將當前字符串**逆序**，拼接到原字符串**末尾**。
輸出：最終字符串。

示例演示

輸入: str="abc", num=2
過程:
第 1 次: "abc" + reverse("abc") = "abc" + "cba" = "abccba"
第 2 次: "abccba" + reverse("abccba") = "abccba" + "abccba" = "abccbaabccba"
輸出: "abccbaabccba"

核心算法：遞歸逆序

遞歸函數 `reverse(s)`：
- 基線條件：長度 ≤ 1 直接返回。
- 遞歸步驟：將字符串對半分割，對右半部分遞歸逆序 + 左半部分遞歸逆序。
這是一種「分治」逆序，異於常規雙指針迭代，但能體現遞歸思想。

完整 Java 代碼實現

import java.util.Scanner;

public class StrMirror {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("請輸入字符串:");
        String str = sc.next(); // 讀取無空格字符串；若含空格用 sc.nextLine()
        System.out.println("str = " + str);

        System.out.println("請輸入逆轉次數：");
        int num = sc.nextInt();

        for (int i = 0; i < num; i++) {
            str = str + reverse(str); // 鏡像拼接
        }

        System.out.println("mirror str = " + str);
        sc.close();
    }

    /**
     * 遞歸實現字符串逆序 (分治法)
     * @param str 待逆序字符串
     * @return 逆序後字符串
     */
    public static String reverse(String str) {
        int length = str.length();
        if (length <= 1) {
            return str; // 基線條件
        }
        // 分割為左右兩半
        String left = str.substring(0, length / 2);
        String right = str.substring(length / 2, length);
        // 遞歸逆序右半 + 遞歸逆序左半
        return reverse(right) + reverse(left);
    }
}

代碼運行示例

請輸入字符串:
abc
str = abc
請輸入逆轉次數：
2
mirror str = abccbaabccba

複雜度分析

• 時間：`reverse` 遞歸深度 log₂N，每層處理所有字符，單次逆序 O(N log N)。循環 `num` 次，總體 O(num * N log N)。(常規雙指針逆序為 O(N))。
• 空間：遞歸棧深度 O(log N)，字符串拼接產生新對象 O(N)。

優化建議 (生產環境)

// 使用 StringBuilder 高效拼接 + 迭代逆序 O(N)
public static String reverseFast(String str) {
    return new StringBuilder(str).reverse().toString();
}

// 主循環優化
StringBuilder sb = new StringBuilder(str);
for (int i = 0; i < num; i++) {
    sb.append(reverseFast(sb.toString()));
}
System.out.println("mirror str = " + sb.toString());

總結

本題考察遞歸思維實現字符串逆序及循環拼接邏輯。教學代碼使用分治遞歸 `reverse`，主流程清晰易懂。實際工程中應優先使用 `StringBuilder.reverse()` 獲得 O(N) 性能並避免棧溢出風險。