这个题解使用了栈的数据结构来解决问题。它从左到右遍历化学式字符串,对于每个字符进行分情况讨论:
1. 如果是左括号,将当前原子入栈,并清空当前原子。
2. 如果是右括号,将当前原子入栈,并清空当前原子。
3. 如果是数字,判断前一个字符是否也是数字,如果是则继续遍历;否则将当前原子和数字作为一个元组入栈,并清空当前原子。如果前一个字符是右括号,则将数字作为括号内原子的系数,将括号内的所有原子依次出栈并乘以系数后重新入栈。
4. 如果是小写字母,将其加入当前原子的名称中。
5. 如果是大写字母,将当前原子入栈,并将该大写字母作为新的当前原子。
遍历完成后,将栈中的所有原子及其数量存入哈希表中,最后按照字典序将哈希表中的原子拼接成字符串返回。
时间复杂度: O(nlogn)
空间复杂度: O(n)
class Solution:
def countOfAtoms(self, formula: str) -> str:
stack = []
last_atom = ""
coef = 1
for i in range(len(formula)):
s = formula[i]
if s == "(":
if last_atom != "": # 将当前原子入栈
stack.append((last_atom, 1))
last_atom = ""
stack.append("(") # 将左括号入栈
elif s == ")":
if last_atom != "": # 将当前原子入栈
stack.append((last_atom, 1))
last_atom = ""
elif s.isnumeric():
if formula[i-1].isnumeric(): # 如果前一个字符也是数字,则继续遍历
continue
j = i + 1
while j < len(formula) and formula[j].isnumeric(): # 找到完整的数字
j += 1
n = int(formula[i:j])
if formula[i-1] != ")": # 如果前一个字符不是右括号,将当前原子和数字作为一个元组入栈
stack.append((last_atom, n))
last_atom = ""
else: # 如果前一个字符是右括号,将数字作为括号内原子的系数
coef = n
temp_stack = []
curr_pair = stack.pop()
while curr_pair != "(": # 将括号内的所有原子依次出栈并乘以系数
temp_stack.append((curr_pair[0], curr_pair[1] * coef))
curr_pair = stack.pop()
for k in range(len(temp_stack)-1, -1, -1): # 将括号内的所有原子重新入栈
stack.append(temp_stack[k])
else:
if s.islower(): # 如果是小写字母,将其加入当前原子的名称中
last_atom += s
if i == len(formula)-1: # 如果是最后一个字符,将当前原子入栈
stack.append((last_atom, 1))
else:
if last_atom == "": # 如果是大写字母,将其作为新的当前原子
last_atom = s
if i == len(formula)-1: # 如果是最后一个字符,将当前原子入栈
stack.append((last_atom, 1))
else: # 如果当前原子不为空,将其入栈,并将该大写字母作为新的当前原子
stack.append((last_atom, 1))
last_atom = s
counter = {}
for pair in stack:
if pair != "(": # 将栈中的所有原子及其数量存入哈希表中
if pair[0] not in counter:
counter[pair[0]] = pair[1]
else:
counter[pair[0]] += pair[1]
res = []
for atom, count in sorted(counter.items()): # 按照字典序将哈希表中的原子拼接成字符串
if count == 1:
res.append(atom)
else:
res.append(atom+str(count))
return "".join(res)