首页 > 代码库 > LeetCode 423. Reconstruct Original Digits from English——学会观察，贪心思路

LeetCode 423. Reconstruct Original Digits from English——学会观察，贪心思路

2024-08-27 23:59:44   219人阅读

Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.

Note:

  1. Input contains only lowercase English letters.
  2. Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as "abc" or "zerone" are not permitted.
  3. Input length is less than 50,000.

Example 1:

Input: "owoztneoer"

Output: "012"

Example 2:

Input: "fviefuro"

Output: "45"

class Solution(object):
    def originalDigits(self, s):
        """
        :type s: str
        :rtype: str
six, zero, two, eight, four中分别包含唯一字母x, z, w, g, u, 根据z,w,x,g,u的个数就可以知道0,2,6,8,4的个数。对于剩下的one,three,five,seven，one可以由字符o的个数减去在0,2,4,6,8中出现的o的个数。
        """
        char_cnt = [0]*26
        for c in s:
            char_cnt[ord(c)-ord(‘a‘)] += 1
        mapp_digits = {"zero": 0, "one": 1, "two": 2, "three": 3, "four": 4, "five": 5, "six": 6, "seven": 7, "eight": 8, "nine": 9}
        digits_c = {"zero": "z", "two": "w", "four": "u", "six": "x",  "eight": "g"}
        digits_c2 = {"one": "o", "three": "h", "five": "f", "seven": "s"}
        digits_c3 = {"nine": "i"}
        out = []
        for digits in (digits_c, digits_c2, digits_c3):
            for d in digits:
                cnt = char_cnt[ord(digits[d])-ord(‘a‘)]
                if cnt > 0:
                    out += [mapp_digits[d]] * cnt
                    for c in d:
                        char_cnt[ord(c)-ord(‘a‘)] -= cnt
        out.sort()
        return "".join(str(c) for c in out)

 

LeetCode 423. Reconstruct Original Digits from English——学会观察，贪心思路


联系
我们