Kimi LeetCode 3614. 用特殊操作处理字符串 II Python3实现

以下是 LeetCode 3614. 用特殊操作处理字符串 II 的 Python3 实现。解题思路倒推法与 Java 版本相同核心思想是1. 正向遍历计算最终字符串长度2. 如果 k 长度返回 .3. 倒序遍历字符串根据操作类型将 k 映射回操作前的位置Python3 实现pythonclass Solution:def processStr(self, s: str, k: int) - str:m 0 # 最终长度# 第一遍正向计算最终长度for c in s:if c *:m max(0, m - 1)elif c #:m 1 # 长度翻倍elif c %:pass # 反转不改变长度else:m 1 # 字母# k 越界if k m:return .# 第二遍倒推找第 k 个字符for i in range(len(s) - 1, -1, -1):c s[i]if c *:# 倒推恢复被删除的字符长度1m 1elif c #:# 倒推长度减半m // 2# 若 k 在右半部分映射到左半部分if k m:k - melif c %:# 倒推反转操作k 变为对称位置k m - 1 - kelse:# 字母长度-1m - 1# 若当前位置就是要找的字符if k m:return creturn .复杂度分析- 时间复杂度O(n)两次遍历字符串- 空间复杂度O(1)仅使用常数额外空间关键点- 长度可能达到 10^{15}Python 的 int 天然支持大整数无需担心溢出问题- 倒推时 * 操作只需恢复长度m 1不需要修改 k- # 操作后若 k 在右半部分k m减去左半长度即可映射回原位置