2025-12-21：用特殊操作處理字符串Ⅰ。用go語言，給定一個只包含小寫字母以及三種特殊符號（*、#、%）的串 s。按從左到右的順序逐個讀取字符，並維護一個初始為空的字符串 result，遇到不同字符時對 result 做相應的更新：

  • 遇到小寫字母：把它接到 result 的末尾；

  • 遇到 '*'：如果 result 非空，則刪除末尾的一個字符；

  • 遇到 '#'：將當前的 result 複製一份並拼接到自身後面；

  • 遇到 '%'：將 result 的字符順序顛倒。

當所有字符處理完畢後，返回最終得到的 result。

1 <= s.length <= 20。

s 只包含小寫英文字母和特殊字符 *、# 和 %。

輸入： s = "a#b%*"。

輸出： "ba"。

解釋：

i s[i] 操作 當前 result
'a' 添加 'a' "a"
1 '#' 複製 result "aa"
2 'b' 添加 'b' "aab"
3 '%' 反轉 result "baa"
4 '*' 刪除最後一個字符 "ba"

因此，最終的 result 是 "ba"。

題目來自力扣3612。

📝 逐步處理過程

  1. 初始狀態

    • 維護一個初始為空的字節切片 ans（對應題目描述中的字符串 result）。

  2. 處理第 1 個字符 'a' (索引 0)

    • 字符 'a' 是小寫字母。
    • 操作：將 'a' 添加到 ans 的末尾。
    • 結果：ans 變為 "a"。

  3. 處理第 2 個字符 '#' (索引 1)

    • 字符 '#' 是特殊符號。
    • 操作：將當前的 ans 複製一份並拼接到自身後面。具體實現是 ans = append(ans, ans...)，這會將 ans 切片中的所有元素追加到其末尾。
    • 結果：ans 從 "a" 變為 "aa"。

  4. 處理第 3 個字符 'b' (索引 2)

    • 字符 'b' 是小寫字母。
    • 操作：將 'b' 添加到 ans 的末尾。
    • 結果：ans 從 "aa" 變為 "aab"。

  5. 處理第 4 個字符 '%' (索引 3)

    • 字符 '%' 是特殊符號。
    • 操作：將 ans 的字符順序顛倒。代碼中使用 slices.Reverse(ans) 實現，該函數會將切片中的元素進行原地反轉。
    • 結果：ans 從 "aab" 反轉為 "baa"。

  6. 處理第 5 個字符 '*' (索引 4)

    • 字符 '*' 是特殊符號。
    • 操作：如果 ans 非空，則刪除其末尾的一個字符。代碼中通過 ans = ans[:len(ans)-1] 實現，這會創建一個不包含最後一個元素的新切片視圖。
    • 結果：ans 從 "baa" 刪除末尾的 'a' 後變為 "ba"。

  7. 最終結果

    • 所有字符處理完畢後，將字節切片 ans 轉換為字符串並返回。
    • 最終結果："ba"。

⏱️ 複雜度分析

時間複雜度：O(n²)

  • 我們需要按順序處理輸入字符串 s 中的每一個字符（共 n 個操作）。
  • 大部分操作（如添加普通字符、刪除末尾字符）的時間複雜度是 O(1)。
  • 但是，有兩個操作會導致較高的時間複雜度：
    1. 遇到 '#' (複製)：ans = append(ans, ans...) 操作需要將當前 ans 的全部內容複製一份。在最壞情況下，如果 ans 的長度是 L，這個操作的時間複雜度是 O(L)。
    2. 遇到 '%' (反轉)：slices.Reverse(ans) 操作需要遍歷切片的一半進行元素交換。如果 ans 的長度是 L，這個操作的時間複雜度是 O(L)。
  • 在極端情況下（例如連續的 '#' 操作），ans 的長度 L 可能會達到 O(n) 級別。因此，整個處理過程的最壞情況時間複雜度是 **O(n²)**。

空間複雜度：O(n)

  • 主要的額外空間是存儲結果的字節切片 ans。
  • 根據題目，輸入字符串長度 n ≤ 20。在最壞情況下（例如幾乎全是字母和 '#'），ans 的最大長度也是 O(n) 級別。
  • 因此，總的額外空間複雜度是 **O(n)**。

Go完整代碼如下：

package main

import (
	"fmt"
	"slices"
)

func processStr(s string) string {
	ans := []byte{}
	for _, c := range s {
		if c == '*' {
			if len(ans) > 0 {
				ans = ans[:len(ans)-1]
			}
		} else if c == '#' {
			ans = append(ans, ans...)
		} else if c == '%' {
			slices.Reverse(ans)
		} else {
			ans = append(ans, byte(c))
		}
	}
	return string(ans)
}

func main() {
	s := "a#b%*"
	result := processStr(s)
	fmt.Println(result)
}

在這裏插入圖片描述

Python完整代碼如下：

# -*-coding:utf-8-*-

def process_str(s: str) -> str:
    ans = []
    for c in s:
        if c == '*':
            ans = ans[:-1] if ans else []
        elif c == '#':
            ans = ans * 2  # 直接複製
        elif c == '%':
            ans = ans[::-1]  # 反轉
        else:
            ans.append(c)
    return ''.join(ans)

if __name__ == "__main__":
    s = "a#b%*"
    result = process_str(s)
    print(result)

在這裏插入圖片描述

C++完整代碼如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

std::string processStr(const std::string& s) {
    std::vector<char> ans;
    for (char c : s) {
        if (c == '*') {
            if (!ans.empty()) {
                ans.pop_back();
            }
        } else if (c == '#') {
            size_t size = ans.size();
            ans.reserve(size * 2);
            for (size_t i = 0; i < size; i++) {
                ans.push_back(ans[i]);
            }
        } else if (c == '%') {
            std::reverse(ans.begin(), ans.end());
        } else {
            ans.push_back(c);
        }
    }
    return std::string(ans.begin(), ans.end());
}

int main() {
    std::string s = "a#b%*";
    std::string result = processStr(s);
    std::cout << result << std::endl;
    return 0;
}

在這裏插入圖片描述