Medium

题目描述

给你一个由小写英文字母和特殊字符 *、#、% 组成的字符串 s。

根据以下规则从左到右处理 s 来构建一个新字符串 result：

  • 如果字符是小写英文字母，将其追加到 result 中。
  • * 会移除 result 中的最后一个字符（如果存在的话）。
  • # 会复制当前的 result 并将其追加到自身。
  • % 会反转当前的 result。

返回处理完 s 中所有字符后的最终字符串 result。

示例 1：

输入：s = "a#b%*"
输出："ba"
解释：
| i | s[i] | 操作 | 当前结果 |
|---|------|------|----------|
| 0 | 'a'  | 追加 'a' | "a" |
| 1 | '#'  | 复制结果 | "aa" |
| 2 | 'b'  | 追加 'b' | "aab" |
| 3 | '%'  | 反转结果 | "baa" |
| 4 | '*'  | 移除最后字符 | "ba" |

示例 2：

输入：s = "z*#"
输出：""
解释：
| i | s[i] | 操作 | 当前结果 |
|---|------|------|----------|
| 0 | 'z'  | 追加 'z' | "z" |
| 1 | '*'  | 移除最后字符 | "" |
| 2 | '#'  | 复制字符串 | "" |

约束条件：

  • 1 <= s.length <= 20
  • s 只包含小写英文字母和特殊字符 *、#、%。

解题思路

这是一道字符串模拟题，核心思路是按照题目描述的规则逐一处理输入字符串中的每个字符。

解题思路：

  1. 初始化结果字符串：创建一个空字符串作为结果容器
  2. 逐字符处理：遍历输入字符串的每个字符，根据字符类型执行相应操作：
    • 普通字母：直接追加到结果字符串末尾
    • * 操作：删除结果字符串的最后一个字符（需检查字符串是否为空）
    • # 操作：将当前结果字符串复制一份并追加到自身后面
    • % 操作：将当前结果字符串进行反转

实现要点：

  • 对于删除操作，需要先判断字符串是否为空，避免越界
  • 字符串反转可以使用语言内置的反转函数
  • 整个过程是线性的模拟，时间复杂度主要取决于字符串操作的复杂度

这种模拟类题目的关键在于仔细理解题意，按部就班地实现每个操作规则，注意边界情况的处理。

代码实现

class Solution {
public:
    string processStr(string s) {
        string result = "";
        
        for (char c : s) {
            if (c >= 'a' && c <= 'z') {
                result += c;
            } else if (c == '*') {
                if (!result.empty()) {
                    result.pop_back();
                }
            } else if (c == '#') {
                result += result;
            } else if (c == '%') {
                reverse(result.begin(), result.end());
            }
        }
        
        return result;
    }
};

class Solution:
    def processStr(self, s: str) -> str:
        result = ""
        
        for c in s:
            if c.islower():
                result += c
            elif c == '*':
                if result:
                    result = result[:-1]
            elif c == '#':
                result += result
            elif c == '%':
                result = result[::-1]
        
        return result

public class Solution {
    public string ProcessStr(string s) {
        string result = "";
        
        foreach (char c in s) {
            if (char.IsLower(c)) {
                result += c;
            } else if (c == '*') {
                if (result.Length > 0) {
                    result = result.Substring(0, result.Length - 1);
                }
            } else if (c == '#') {
                result += result;
            } else if (c == '%') {
                char[] arr = result.ToCharArray();
                Array.Reverse(arr);
                result = new string(arr);
            }
        }
        
        return result;
    }
}

/**
 * @param {string} s
 * @return {string}
 */
var processStr = function(s) {
    let result = "";
    
    for (let char of s) {
        if (char >= 'a' && char <= 'z') {
            result += char;
        } else if (char === '*') {
            if (result.length > 0) {
                result = result.slice(0, -1);
            }
        } else if (char === '#') {
            result = result + result;
        } else if (char === '%') {
            result = result.split('').reverse().join('');
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²)，其中 n 是字符串长度。最坏情况下，每次 # 操作都会使结果字符串长度翻倍，导致总操作次数达到 O(n²)
空间复杂度O(n²)，最坏情况下连续的 # 操作会使结果字符串长度指数增长，但由于输入长度限制为 20，实际空间使用是有界的