LeetCode Python, Java, C++  >  3614. 处理包含特殊操作的字符串 II  >  已支持 Python, Java, JavaScript, C++, C#, Go, Ruby, Rust, Kotlin, Swift  >  GitHub

    力扣链接：3614. 处理包含特殊操作的字符串 II，难度等级：困难。

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

    同时给你一个整数 k。

    通过从左到右处理 s ，按照以下规则构建一个新字符串 result ：

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

    返回最终字符串 result 的第 k 个字符（从 0 开始计数，或者根据题意如果是0-indexed，请视同 0-indexed）。如果 k 超出 result 的边界，则返回 '.'。

    示例 1:

    输入: s = "a#b%*", k = 1

    输出: "a"

    解释:

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

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

    示例 2:

    输入: s = "cd%#*#", k = 3

    输出: "d"

    解释:

    i s[i] 操作 当前 result
    0 'c' 追加 'c' "c"
    1 'd' 追加 'd' "cd"
    2 '%' 反转 result "dc"
    3 '#' 复制 result "dcdc"
    4 '*' 删除最后一个字符 "dcd"
    5 '#' 复制 result "dcddcd"

    最终的 result 是 "dcddcd"。索引 k = 3 处的字符是 'd'。

    示例 3:

    输入: s = "z*#", k = 0

    输出: "."

    解释:

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

    最终的 result 是 ""。因为索引 k = 0 越界，输出为 '.'。

    约束:

    • 1 <= s.length <= 10^5
    • s 仅由小写英文字母和特殊字符 '*'、'#' 以及 '%' 组成。
    • 0 <= k <= 10^{15}
    • 处理 s 后 result 的长度不会超过 10^{15}。
    相关标签

    字符串 模拟

    提示 1

    Track the length of the string after each operation on s.

    提示 2

    Walk backwards through s, undoing each # by using modulus on the tracked lengths, and undoing each % by mirroring across the midpoint, to pinpoint the kth character.

    思路
    上一题下一题

    由于 k 的最大值可以达到 10^{15}，我们无法直接模拟字符串的构建过程，否则会导致内存超限（MLE）或时间超限（TLE）。

    相反，我们可以使用反向模拟法：

    1. 首先，计算在处理 s 的每一步时字符串的长度。
    2. 如果最终长度小于或等于 k，说明索引越界，直接返回 '.'。
    3. 否则，我们从后往前遍历字符串。在每一步 i：
      • 如果 s[i] 是字母：检查它是否是我们要找的字符（即 lens[i] - 1 == k）。如果是，则返回它。
      • 如果 s[i] == '#'（复制）：字符串被复制了一份。如果 k 落在后半部分，它对应于前半部分的同一个字符。所以我们更新 k = k % (lens[i] / 2)。
      • 如果 s[i] == '%'（反转）：字符串被反转了。我们将 k 更新为反转前的对应索引：k = lens[i] - 1 - k。
      • 如果 s[i] == '*'（删除）：我们不需要改变 k。因为 k 是当前字符串中的一个有效索引，而 * 只是删除了最末尾的一个字符，我们当前的 k 自然指向在此 * 之前添加的字符。

    这个逻辑保证了 k 始终是当前步骤字符串中的一个有效索引。

    👋 站长寄语：我还为你开发了 coder.id - 打造程序员个人IP， 包含作品集、简历和博客等，助您顺利拿到 Offer！

    步骤

    1. 创建一个大小为 n 的数组 lens，用于存储每一步的字符串长度。
    2. 初始化 curr_len = 0。
    3. 从左到右遍历 s：
      • 如果 s[i] 是字母，curr_len 加 1。
      • 如果 s[i] == '*'，curr_len 减 1（最小为 0）。
      • 如果 s[i] == '#'，curr_len 乘以 2。
      • 将 curr_len 存入 lens[i]。
    4. 如果 curr_len <= k，返回 '.'。
    5. 从右到左遍历 s：
      • 如果 s[i] 是字母且 lens[i] - 1 == k，返回 s[i]。
      • 如果 s[i] == '#' 且 k >= lens[i] / 2，更新 k %= (lens[i] / 2)。
      • 如果 s[i] == '%'，更新 k = lens[i] - 1 - k。

    复杂度

    时间复杂度

    O(n)

    空间复杂度

    O(n)

    解释

    • 时间复杂度： O(n)，其中 n 是字符串 s 的长度。我们对字符串进行了两次遍历。
    • 空间复杂度： O(n)，用于在 lens 数组中存储每一步的长度。

    题解语言： Python Java JavaScript C++ C# Go Ruby Rust Kotlin Swift

    Python # 

    class Solution:
    def processStr(self, s: str, k: int) -> str:
        lens = []
        curr_len = 0
        for ch in s:
            if ch.isalpha():
                curr_len += 1
            elif ch == '*':
                curr_len = max(0, curr_len - 1)
            elif ch == '#':
                curr_len *= 2
            elif ch == '%':
                pass
            lens.append(curr_len)

        if curr_len <= k:
            return '.'

        for i in range(len(s) - 1, -1, -1):
            if s[i].isalpha():
                if lens[i] - 1 == k:
                    return s[i]
            elif s[i] == '#':
                half = lens[i] // 2
                if half > 0 and k >= half:
                    k %= half
            elif s[i] == '%':
                if lens[i] > 0:
                    k = lens[i] - 1 - k

        return '.'

    Java # 

    class Solution {
    public char processStr(String s, long k) {
        int n = s.length();
        long[] lens = new long[n];
        long currLen = 0;

        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (ch >= 'a' && ch <= 'z') {
                currLen++;
            } else if (ch == '*') {
                currLen = Math.max(0L, currLen - 1);
            } else if (ch == '#') {
                currLen *= 2;
            }
            lens[i] = currLen;
        }

        if (currLen <= k) {
            return '.';
        }

        for (int i = n - 1; i >= 0; i--) {
            char ch = s.charAt(i);
            if (ch >= 'a' && ch <= 'z') {
                if (lens[i] - 1 == k) {
                    return ch;
                }
            } else if (ch == '#') {
                long half = lens[i] / 2;
                if (half > 0 && k >= half) {
                    k %= half;
                }
            } else if (ch == '%') {
                if (lens[i] > 0) {
                    k = lens[i] - 1 - k;
                }
            }
        }

        return '.';
    }
}

    JavaScript # 

    /**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var processStr = function(s, k) {
    const n = s.length;
    const lens = new Array(n);
    let currLen = 0n;
    let bigK = BigInt(k);

    for (let i = 0; i < n; i++) {
        const ch = s[i];
        if (ch >= 'a' && ch <= 'z') {
            currLen++;
        } else if (ch === '*') {
            if (currLen > 0n) currLen--;
        } else if (ch === '#') {
            currLen *= 2n;
        }
        lens[i] = currLen;
    }

    if (currLen <= bigK) {
        return '.';
    }

    for (let i = n - 1; i >= 0; i--) {
        const ch = s[i];
        if (ch >= 'a' && ch <= 'z') {
            if (lens[i] - 1n === bigK) {
                return ch;
            }
        } else if (ch === '#') {
            const half = lens[i] / 2n;
            if (half > 0n && bigK >= half) {
                bigK %= half;
            }
        } else if (ch === '%') {
            if (lens[i] > 0n) {
                bigK = lens[i] - 1n - bigK;
            }
        }
    }

    return '.';
};

    C++ # 

    class Solution {
public:
    char processStr(string s, long long k) {
        int n = s.length();
        vector<long long> lens(n);
        long long curr_len = 0;

        for (int i = 0; i < n; ++i) {
            char ch = s[i];
            if (ch >= 'a' && ch <= 'z') {
                curr_len++;
            } else if (ch == '*') {
                curr_len = max(0LL, curr_len - 1);
            } else if (ch == '#') {
                curr_len *= 2;
            }
            lens[i] = curr_len;
        }

        if (curr_len <= k) return '.';

        for (int i = n - 1; i >= 0; --i) {
            char ch = s[i];
            if (ch >= 'a' && ch <= 'z') {
                if (lens[i] - 1 == k) return ch;
            } else if (ch == '#') {
                long long half = lens[i] / 2;
                if (half > 0 && k >= half) k %= half;
            } else if (ch == '%') {
                if (lens[i] > 0) k = lens[i] - 1 - k;
            }
        }

        return '.';
    }
};

    C# # 

    public class Solution {
    public char ProcessStr(string s, long k) {
        int n = s.Length;
        long[] lens = new long[n];
        long currLen = 0;

        for (int i = 0; i < n; i++) {
            char ch = s[i];
            if (ch >= 'a' && ch <= 'z') {
                currLen++;
            } else if (ch == '*') {
                currLen = Math.Max(0L, currLen - 1);
            } else if (ch == '#') {
                currLen *= 2;
            }
            lens[i] = currLen;
        }

        if (currLen <= k) return '.';

        for (int i = n - 1; i >= 0; i--) {
            char ch = s[i];
            if (ch >= 'a' && ch <= 'z') {
                if (lens[i] - 1 == k) return ch;
            } else if (ch == '#') {
                long half = lens[i] / 2;
                if (half > 0 && k >= half) k %= half;
            } else if (ch == '%') {
                if (lens[i] > 0) k = lens[i] - 1 - k;
            }
        }

        return '.';
    }
}

    Go # 

    func processStr(s string, k int64) byte {
    n := len(s)
    lens := make([]int64, n)
    var currLen int64 = 0

    for i := 0; i < n; i++ {
        ch := s[i]
        if ch >= 'a' && ch <= 'z' {
            currLen++
        } else if ch == '*' {
            if currLen > 0 {
                currLen--
            }
        } else if ch == '#' {
            currLen *= 2
        }
        lens[i] = currLen
    }

    if currLen <= k {
        return '.'
    }

    for i := n - 1; i >= 0; i-- {
        ch := s[i]
        if ch >= 'a' && ch <= 'z' {
            if lens[i] - 1 == k {
                return ch
            }
        } else if ch == '#' {
            half := lens[i] / 2
            if half > 0 && k >= half {
                k %= half
            }
        } else if ch == '%' {
            if lens[i] > 0 {
                k = lens[i] - 1 - k
            }
        }
    }

    return '.'
}

    Ruby # 

    # @param {String} s
# @param {Integer} k
# @return {String}
def process_str(s, k)
    n = s.length
    lens = Array.new(n)
    curr_len = 0

    (0...n).each do |i|
        ch = s[i]
        if ch >= 'a' && ch <= 'z'
            curr_len += 1
        elsif ch == '*'
            curr_len = [0, curr_len - 1].max
        elsif ch == '#'
            curr_len *= 2
        end
        lens[i] = curr_len
    end

    return '.' if curr_len <= k

    (n - 1).downto(0) do |i|
        ch = s[i]
        if ch >= 'a' && ch <= 'z'
            return ch if lens[i] - 1 == k
        elsif ch == '#'
            half = lens[i] / 2
            k %= half if half > 0 && k >= half
        elsif ch == '%'
            k = lens[i] - 1 - k if lens[i] > 0
        end
    end

    '.'
end

    Rust # 

    impl Solution {
    pub fn process_str(s: String, mut k: i64) -> char {
        let n = s.len();
        let mut lens = vec![0i64; n];
        let mut curr_len = 0i64;
        let bytes = s.as_bytes();

        for i in 0..n {
            let ch = bytes[i];
            if ch >= b'a' && ch <= b'z' {
                curr_len += 1;
            } else if ch == b'*' {
                if curr_len > 0 { curr_len -= 1; }
            } else if ch == b'#' {
                curr_len *= 2;
            }
            lens[i] = curr_len;
        }

        if curr_len <= k {
            return '.';
        }

        for i in (0..n).rev() {
            let ch = bytes[i];
            if ch >= b'a' && ch <= b'z' {
                if lens[i] - 1 == k {
                    return ch as char;
                }
            } else if ch == b'#' {
                let half = lens[i] / 2;
                if half > 0 && k >= half {
                    k %= half;
                }
            } else if ch == b'%' {
                if lens[i] > 0 {
                    k = lens[i] - 1 - k;
                }
            }
        }

        '.'
    }
}

    Kotlin # 

    class Solution {
    fun processStr(s: String, k: Long): Char {
        var mutableK = k
        val n = s.length
        val lens = LongArray(n)
        var currLen = 0L

        for (i in 0 until n) {
            val ch = s[i]
            if (ch in 'a'..'z') {
                currLen++
            } else if (ch == '*') {
                if (currLen > 0) currLen--
            } else if (ch == '#') {
                currLen *= 2
            }
            lens[i] = currLen
        }

        if (currLen <= mutableK) return '.'

        for (i in n - 1 downTo 0) {
            val ch = s[i]
            if (ch in 'a'..'z') {
                if (lens[i] - 1 == mutableK) return ch
            } else if (ch == '#') {
                val half = lens[i] / 2
                if (half > 0 && mutableK >= half) mutableK %= half
            } else if (ch == '%') {
                if (lens[i] > 0) mutableK = lens[i] - 1 - mutableK
            }
        }

        return '.'
    }
}

    Swift # 

    class Solution {
    func processStr(_ s: String, _ k: Int) -> Character {
        var mutableK = k
        let chars = Array(s)
        let n = chars.count
        var lens = [Int](repeating: 0, count: n)
        var currLen = 0

        for i in 0..<n {
            let ch = chars[i]
            if ch >= "a" && ch <= "z" {
                currLen += 1
            } else if ch == "*" {
                currLen = max(0, currLen - 1)
            } else if ch == "#" {
                currLen *= 2
            }
            lens[i] = currLen
        }

        if currLen <= mutableK {
            return "."
        }

        for i in stride(from: n - 1, through: 0, by: -1) {
            let ch = chars[i]
            if ch >= "a" && ch <= "z" {
                if lens[i] - 1 == mutableK {
                    return ch
                }
            } else if ch == "#" {
                let half = lens[i] / 2
                if half > 0 && mutableK >= half {
                    mutableK %= half
                }
            } else if ch == "%" {
                if lens[i] > 0 {
                    mutableK = lens[i] - 1 - mutableK
                }
            }
        }

        return "."
    }
}
    题解语言： Python Java JavaScript C++ C# Go Ruby Rust Kotlin Swift

    其它语言

    欢迎贡献代码到 GitHub repo -> 3614. 处理包含特殊操作的字符串 II。感谢！
    上一题下一题

    打造你的开发者个人IP

    • 📄 简历 + 作品集 + 博客
    • 🌐 支持绑定自定义域名
    • ✨ 顶级子域名： https://yourname.coder.id

    立即前往 coder.id 打造你的开发者个人IP →