Hard

题目描述

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

同时给定一个整数 k。

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

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

返回最终字符串 result 的第 k 个字符。如果 k 超出了 result 的边界，返回 ‘.’。

示例 1：

输入：s = "a#b%*", k = 1
输出："a"
解释：
- 处理 'a'：追加 'a' → result = "a"
- 处理 '#'：复制结果 → result = "aa"  
- 处理 'b'：追加 'b' → result = "aab"
- 处理 '%'：反转结果 → result = "baa"
- 处理 '*'：移除最后字符 → result = "ba"

最终结果是 "ba"，索引 k = 1 处的字符是 'a'。

示例 2：

输入：s = "cd%#*#", k = 3
输出："d"

示例 3：

输入：s = "z*#", k = 0
输出："."

约束条件：

  • 1 <= s.length <= 10^5
  • s 只包含小写英文字母和特殊字符 ‘*’、’#’、’%’
  • 0 <= k <= 10^15
  • 处理 s 后结果的长度不会超过 10^15

解题思路

这道题的关键在于理解字符串长度可能达到 10^15，直接模拟会导致内存和时间复杂度过高。我们需要采用逆向思维来解决。

核心思路：

  1. 正向计算长度：首先遍历字符串，计算每一步操作后的字符串长度，但不构建实际字符串
  2. 逆向定位字符：从后往前遍历操作，根据当前位置 k 和字符串长度来逆推原始位置

逆向操作规则：

  • 遇到 #：当前长度是前一步的2倍，通过取模运算确定 k 在前半部分还是后半部分
  • 遇到 %：反转操作，k 的新位置为 length - 1 - k
  • 遇到 *：长度增加1（逆向看是减少1的逆操作）
  • 遇到字母：如果 k 正好等于当前长度-1，说明找到了目标字符

优化点：

  • 使用长度数组记录每步操作后的长度
  • 逆向遍历时动态调整 k 的位置
  • 特殊处理边界情况（k 超出范围）

这种方法避免了构建巨大字符串，时间复杂度为 O(n)，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    char processStr(string s, long long k) {
        vector<long long> lengths;
        long long len = 0;
        
        // 正向计算每步的长度
        for (char c : s) {
            if (c >= 'a' && c <= 'z') {
                len++;
            } else if (c == '*') {
                len = max(0LL, len - 1);
            } else if (c == '#') {
                len *= 2;
            } else if (c == '%') {
                // 反转不改变长度
            }
            lengths.push_back(len);
        }
        
        if (k >= len) return '.';
        
        // 逆向查找
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s[i] >= 'a' && s[i] <= 'z') {
                if (k == lengths[i] - 1) {
                    return s[i];
                }
            } else if (s[i] == '*') {
                k++;
            } else if (s[i] == '#') {
                long long prevLen = (i > 0) ? lengths[i-1] : 0;
                k %= prevLen;
            } else if (s[i] == '%') {
                long long currentLen = (i > 0) ? lengths[i-1] : 0;
                k = currentLen - 1 - k;
            }
        }
        
        return '.';
    }
};

class Solution:
    def processStr(self, s: str, k: int) -> str:
        lengths = []
        length = 0
        
        # 正向计算每步的长度
        for c in s:
            if c.islower():
                length += 1
            elif c == '*':
                length = max(0, length - 1)
            elif c == '#':
                length *= 2
            elif c == '%':
                # 反转不改变长度
                pass
            lengths.append(length)
        
        if k >= length:
            return '.'
        
        # 逆向查找
        for i in range(len(s) - 1, -1, -1):
            if s[i].islower():
                if k == lengths[i] - 1:
                    return s[i]
            elif s[i] == '*':
                k += 1
            elif s[i] == '#':
                prev_len = lengths[i-1] if i > 0 else 0
                k %= prev_len
            elif s[i] == '%':
                current_len = lengths[i-1] if i > 0 else 0
                k = current_len - 1 - k
        
        return '.'

public class Solution {
    public char ProcessStr(string s, long k) {
        List<long> lengths = new List<long>();
        long length = 0;
        
        // 正向计算每步的长度
        foreach (char c in s) {
            if (char.IsLower(c)) {
                length++;
            } else if (c == '*') {
                length = Math.Max(0, length - 1);
            } else if (c == '#') {
                length *= 2;
            } else if (c == '%') {
                // 反转不改变长度
            }
            lengths.Add(length);
        }
        
        if (k >= length) return '.';
        
        // 逆向查找
        for (int i = s.Length - 1; i >= 0; i--) {
            if (char.IsLower(s[i])) {
                if (k == lengths[i] - 1) {
                    return s[i];
                }
            } else if (s[i] == '*') {
                k++;
            } else if (s[i] == '#') {
                long prevLen = i > 0 ? lengths[i-1] : 0;
                k %= prevLen;
            } else if (s[i] == '%') {
                long currentLen = i > 0 ? lengths[i-1] : 0;
                k = currentLen - 1 - k;
            }
        }
        
        return '.';
    }
}

var processStr = function(s, k) {
    let operations = [];
    let length = 0;
    let reversed = false;
    
    for (let char of s) {
        if (char === '*') {
            if (length > 0) {
                operations.push({type: 'remove'});
                length--;
            }
        } else if (char === '#') {
            operations.push({type: 'duplicate', len: length});
            length *= 2;
        } else if (char === '%') {
            operations.push({type: 'reverse'});
            reversed = !reversed;
        } else {
            operations.push({type: 'add', char: char});
            length++;
        }
    }
    
    if (k >= length) return '.';
    
    function findChar(pos, ops, currentReversed) {
        let currentLen = 0;
        let stack = [];
        
        for (let op of ops) {
            if (op.type === 'add') {
                stack.push({type: 'char', char: op.char, pos: currentLen});
                currentLen++;
            } else if (op.type === 'remove') {
                if (currentLen > 0) {
                    stack.pop();
                    currentLen--;
                }
            } else if (op.type === 'duplicate') {
                let oldLen = op.len;
                if (pos < oldLen) {
                    continue;
                } else {
                    return findChar(pos - oldLen, ops.slice(0, ops.indexOf(op)), currentReversed);
                }
            } else if (op.type === 'reverse') {
                currentReversed = !currentReversed;
                pos = currentLen - 1 - pos;
            }
        }
        
        if (currentReversed) {
            pos = currentLen - 1 - pos;
        }
        
        return stack[pos].char;
    }
    
    let pos = k;
    let currentOps = [...operations];
    let currentReversed = false;
    
    while (true) {
        let newOps = [];
        let currentLen = 0;
        let found = false;
        
        for (let i = 0; i < currentOps.length; i++) {
            let op = currentOps[i];
            
            if (op.type === 'add') {
                if (pos === currentLen) {
                    return op.char;
                }
                newOps.push(op);
                currentLen++;
            } else if (op.type === 'remove') {
                if (currentLen > 0) {
                    newOps.push(op);
                    currentLen--;
                }
            } else if (op.type === 'duplicate') {
                if (pos < currentLen) {
                    currentOps = newOps;
                    found = true;
                    break;
                } else {
                    pos = pos - currentLen;
                    currentOps = newOps;
                    found = true;
                    break;
                }
            } else if (op.type === 'reverse') {
                pos = currentLen - 1 - pos;
                newOps.push(op);
            }
        }
        
        if (!found) {
            currentOps = newOps;
            break;
        }
    }
    
    for (let op of currentOps) {
        if (op.type === 'add' && op.pos === pos) {
            return op.char;
        }
    }
    
    return '.';
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n)
空间复杂度O(n)

其中 n 是字符串 s 的长度。我们需要遍历字符串两次（正向计算长度，逆向查找字符），并使用额外的数组存储每步的长度信息。