题目链接 | 3170. 删除星号以后字典序最小的字符串 |
---|---|
思路 | 堆栈 & 位运算 |
题解链接 | 三种写法:26 个栈+位运算优化(Python/Java/C++/Go) |
关键点 | 1. 用堆栈跟踪各个字母出现的位置 2. 用位运算跟踪当前最小字母(lowbit技巧) |
时间复杂度 | 朴素做法:\(O(n\vert\Sigma\vert)\) 位运算优化:\(O(n+\vert\Sigma\vert)\) |
空间复杂度 | 朴素做法:\(O(n+\vert\Sigma\vert)\) 位运算优化:\(O(n+\vert\Sigma\vert)\) |
代码实现(朴素做法):
class Solution:def clearStars(self, s: str) -> str:s = list(s)stack = [[] for _ in range(26)]for i, ch in enumerate(s):if ch != '*':stack[ord(ch) - ord('a')].append(i)continuefor positions in stack:if positions:s[positions.pop()] = '*'breakreturn "".join(ch for ch in s if ch != "*")
代码实现(位运算优化):
class Solution:def clearStars(self, s: str) -> str:s = list(s)stack = [[] for _ in range(26)]mask = 0for i, ch in enumerate(s):if ch != '*':ch = ord(ch) - ord('a')stack[ch].append(i)mask |= 1 << chelse:lowbit = mask & -maskposition = stack[lowbit.bit_length() - 1]s[position.pop()] = '*'if not position:mask ^= lowbitreturn "".join(ch for ch in s if ch != '*')