Leetcode 726. Number of Atoms

Tyan

发布于 2021-03-02 16:30:57

2940

发布于 2021-03-02 16:30:57

文章被收录于专栏：SnailTyan

文章作者：Tyan 博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

解析：这道题还有优化的空间，这样写主要是逻辑清晰。1. 把元素(多个字母)、数字(多个数字字符)、左右括号拆分开；2. 计算元素的个数，如果元素后没有数字，则添加数字1作为元素个数；当碰到右括号时，查找其对应的左括号，并将其中的元素个数乘以括号后的数字，其后没数字，则默认乘以1；3. 统计元素个数，相同元素个数相加；4. 排序字典，按元素字母排序；5. 构造返回结果字符串。

Version 1

class Solution:
    def countOfAtoms(self, formula):
        stat = {}
        stack = []
        parts = []

        # Split string by alpha, number, '(', ')'
        for index, ch in enumerate(formula):
            if ch.isupper():
                parts.append(ch)
            elif ch.islower():
                parts[-1] += ch
            elif ch.isdigit():
                if formula[index - 1].isdigit():
                    parts[-1] += ch
                else:
                    parts.append(ch)
            else:
                parts.append(ch)

        # Calculate the number of atom and remove '(', ')'
        stack = []
        for index, part in enumerate(parts):
            if part.isalpha():
                if index + 1 == len(parts) or not parts[index + 1].isdigit():
                    stack.append(part)
                    stack.append(1)
                else:
                    stack.append(part)
            elif part.isdigit() and parts[index - 1] != ')':
                    stack.append(int(part))
            elif part == '(':
                stack.append(part)
            elif part == ')':
                if index + 1 < len(parts) and parts[index + 1].isdigit():
                    multiplier = int(parts[index + 1])
                else:
                    multiplier = 1

                i = len(stack) - 1
                while stack[i] != '(':
                    if isinstance(stack[i], int):
                        stack[i] = stack[i] * multiplier
                    i -= 1
                stack.pop(i)

        # Stat the number of atoms
        for i in range(0, len(stack), 2):
            if stack[i] in stat:
                stat[stack[i]] += stack[i + 1]
            else:
                stat[stack[i]] = stack[i + 1]
        stat = sorted(stat.items(), key=lambda item: item[0])
        result = ''
        for key, value in stat:
            if value > 1:
                result = result + key + str(value)
            else:
                result = result + key
        return result