难度: Easy
Submission
运行时间: 34 ms
内存: 16.3 MB
class StringIterator:
def __init__(self, compressedString: str):
self.letters = []
self.counts = []
n = ''
for c in compressedString:
if c.isalpha():
if n:
self.counts.append(int(n))
n = ''
self.letters.append(c)
else:
n += c
if n:
self.counts.append(int(n))
def next(self) -> str:
if self.hasNext():
ret = self.letters[0]
self.counts[0] -= 1
if self.counts[0] == 0:
self.letters.pop(0)
self.counts.pop(0)
return ret
return ' '
def hasNext(self) -> bool:
return len(self.letters) > 0 and len(self.counts) > 0
# Your StringIterator object will be instantiated and called as such:
# obj = StringIterator(compressedString)
# param_1 = obj.next()
# param_2 = obj.hasNext()
Explain
这个题解的思路是将压缩字符串解压缩并逐个字符返回。在初始化时，它将字符串解析为两个列表：letters 存储字符，counts 存储对应的计数。next() 方法每次返回一个字符，并将对应的计数减 1。当计数减为 0 时，将当前字符和计数从列表中移除。hasNext() 方法判断是否还有剩余的字符可以返回。
时间复杂度: O(n)
空间复杂度: O(n)
class StringIterator:
def __init__(self, compressedString: str):
self.letters = [] # 存储字符
self.counts = [] # 存储对应的计数
n = ''
for c in compressedString:
if c.isalpha():
if n:
self.counts.append(int(n))
n = ''
self.letters.append(c)
else:
n += c
if n:
self.counts.append(int(n))
def next(self) -> str:
if self.hasNext():
ret = self.letters[0]
self.counts[0] -= 1
if self.counts[0] == 0:
self.letters.pop(0)
self.counts.pop(0)
return ret
return ' '
def hasNext(self) -> bool:
return len(self.letters) > 0 and len(self.counts) > 0
Explore
在解析压缩字符串的过程中，我通过遍历每个字符，并检测是否是字母。如果是字母，首先检查临时变量 `n`（用于存放数字）是否非空，如果非空，则说明前一个字符的计数已完整，因此将它转换为整数后添加到 `counts` 列表中，并清空 `n` 以用于下一个数字的累加。如果不是字母，则将字符累加到 `n` 中。这样可以确保即使是多位数也能被正确解析并与前一个字母匹配。最后，循环结束后，还需要检查 `n` 是否非空，以确保最后一个字符的计数也被添加。
当前的解法在初始化时需要遍历整个字符串并构建两个列表 `letters` 和 `counts`，如果输入的字符串非常大，这将导致较高的内存消耗和初始化时间。对于大规模数据，一种更高效的方法是使用生成器或迭代器直接在原始字符串上操作，避免一次性解析整个字符串，而是在调用 `next()` 方法时才逐步解析和返回字符。这样可以大幅减少内存使用，并提高处理大数据的效率。
在 `next()` 函数中返回空格是一种表示没有更多字符可返回的方法。这种设计简单且能够在多数情况下清晰地表明迭代器已经到达尽头。然而，这种设计在处理需要区分空白字符和实际数据的场景中可能导致混淆。例如，在文本解析或编程语言的语法分析中，返回的空格可能被误解为有效数据的一部分。更严谨的设计应返回一个明确的信号，如 `None` 或抛出一个异常，以避免这种潜在的混淆。
当前的 `hasNext()` 实现通过检查 `letters` 和 `counts` 列表的长度是否大于0来确定是否还有未返回的字符。这种方式在大多数情况下是充分的。然而，它假设 `letters` 和 `counts` 列表长度始终保持同步。如果由于某种错误导致两个列表的长度不匹配，这种检查方式可能会引发错误。确保这两个列表在所有操作中都严格同步是很重要的，任何操作导致长度不一致都应该被视为实现错误。