跳转至

3612. 用特殊操作处理字符串 I

题目描述

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

请根据以下规则从左到右处理 s 中的字符，构造一个新的字符串 result：

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

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

 

示例 1：

输入： s = "a#b%*"

输出： "ba"

解释：

i s[i] 操作 当前 result
0 'a' 添加 'a' "a"
1 '#' 复制 result "aa"
2 'b' 添加 'b' "aab"
3 '%' 反转 result "baa"
4 '*' 删除最后一个字符 "ba"

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

示例 2：

输入： s = "z*#"

输出： ""

解释：

i s[i] 操作 当前 result
0 'z' 添加 'z' "z"
1 '*' 删除最后一个字符 ""
2 '#' 复制字符串 ""

因此，最终的 result 是 ""。

 

提示:

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

解法

方法一：模拟

我们直接模拟题目中的操作即可。我们使用一个列表 \(\text{result}\) 来存储当前的结果字符串。遍历输入字符串 \(s\) 中的每个字符，根据字符的类型执行相应的操作：

  • 如果字符是小写英文字母，则将其添加到 \(\text{result}\) 中。
  • 如果字符是 *，则删除 \(\text{result}\) 中的最后一个字符（如果存在）。
  • 如果字符是 #，则将 \(\text{result}\) 复制一遍并追加到其自身后面。
  • 如果字符是 %，则反转 \(\text{result}\)。

最后，我们将 \(\text{result}\) 转换为字符串并返回。

时间复杂度 \(O(2^n)\)，其中 \(n\) 是字符串 \(s\) 的长度。最坏情况下，可能会因为 # 操作导致 \(\text{result}\) 的长度每次翻倍，因此时间复杂度是指数级的。忽略答案的空间消耗，空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def processStr(self, s: str) -> str:
        result = []
        for c in s:
            if c.isalpha():
                result.append(c)
            elif c == "*" and result:
                result.pop()
            elif c == "#":
                result.extend(result)
            elif c == "%":
                result.reverse()
        return "".join(result)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public String processStr(String s) {
        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetter(c)) {
                result.append(c);
            } else if (c == '*') {
                result.setLength(Math.max(0, result.length() - 1));
            } else if (c == '#') {
                result.append(result);
            } else if (c == '%') {
                result.reverse();
            }
        }
        return result.toString();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string processStr(string s) {
        string result;
        for (char c : s) {
            if (isalpha(c)) {
                result += c;
            } else if (c == '*') {
                if (!result.empty()) {
                    result.pop_back();
                }
            } else if (c == '#') {
                result += result;
            } else if (c == '%') {
                ranges::reverse(result);
            }
        }
        return result;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func processStr(s string) string {
    var result []rune
    for _, c := range s {
        if unicode.IsLetter(c) {
            result = append(result, c)
        } else if c == '*' {
            if len(result) > 0 {
                result = result[:len(result)-1]
            }
        } else if c == '#' {
            result = append(result, result...)
        } else if c == '%' {
            slices.Reverse(result)
        }
    }
    return string(result)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function processStr(s: string): string {
    const result: string[] = [];
    for (const c of s) {
        if (/[a-zA-Z]/.test(c)) {
            result.push(c);
        } else if (c === '*') {
            if (result.length > 0) {
                result.pop();
            }
        } else if (c === '#') {
            result.push(...result);
        } else if (c === '%') {
            result.reverse();
        }
    }
    return result.join('');
}

评论