LeetCode 423: Reconstruct Original Digits from English Solution in Python – A Step-by-Step Guide

What Is LeetCode 423: Reconstruct Original Digits from English?

In LeetCode 423: Reconstruct Original Digits from English, you’re given a string s (e.g., "eighthree") that’s a concatenation of English words for digits 0-9 ("zero", "one", "two", ..., "nine"), possibly out of order. Your task is to return the original digits as a string in ascending order (e.g., "38"). The input contains exactly the letters needed for some combination of these words, and each digit’s English name has unique letter patterns—like 'z' only in "zero" or 'w' only in "two." For "eighthree," the letters (e:3, i:1, g:1, h:2, t:1, r:1) match "eight" (e,i,g,h,t) and "three" (t,h,r,e,e), yielding "38."

Problem Statement

• Input: A string s (mixed English digit words).
• Output: A string—the original digits in ascending order.
• Rules:
• s contains letters from digit words 0-9.
• Each digit’s letters match its English name exactly.
• Output digits in sorted order.

Constraints

• 0 <= s.length <= 10⁵.
• s consists of lowercase English letters.
• s can be mapped back to original digits.

Examples

• Input: s = "owoztneoer"
• Output: "012" ("zero", "two", "one").
• Input: s = "fviefuro"
• Output: "45" ("five", "four").
• Input: s = "eighthree"
• Output: "38" ("eight", "three").

Understanding the Problem: Decoding the Digits

To solve LeetCode 423: Reconstruct Original Digits from English in Python, we need to extract digits 0-9 from a jumbled string of their English names and sort them. A naive idea might be to guess all possible word combos—but with up to 10⁵ characters, that’s impractical! Instead, we’ll use:

• Best Solution (Greedy with Unique Letter Counting): O(n) time, O(1) space—leverages unique letters.
• Alternative Solution (Brute Force with Permutations): O(n! * n) time, O(n)—tries all possibilities.

Let’s dive into the greedy solution with a clear, step-by-step explanation.

Best Solution: Greedy with Unique Letter Counting

Why This Is the Best Solution

The greedy with unique letter counting method is the top pick because it’s fast—O(n) time, O(1) space—and cleverly exploits unique letters in digit words to decode them in a smart order. It counts letters, identifies digits with distinct markers (e.g., 'z' for "zero"), subtracts their letters, and repeats until all digits are found, sorting them at the end. It’s like solving a word puzzle by picking out giveaway clues first!

How It Works

Think of the string as a letter soup you’re decoding:

• Step 1: Count Letters:
• Build a frequency map of all characters in s.
• Step 2: Identify Digits Greedily:
• Use unique letters to spot digits:
• 'z': "zero" (0).
• 'w': "two" (2).
• 'u': "four" (4).
• 'x': "six" (6).
• 'g': "eight" (8).
• 'h': "three" (3, after 8).
• 'f': "five" (5, after 4).
• 's': "seven" (7, after 6).
• 'i': "nine" (9, after 5, 6, 8).
• 'n': "one" (1, after 9).
• Subtract each digit’s letters from the count.
• Step 3: Build Result:
• Sort digits (0-9) based on counts.
• Step 4: Why This Works:
• Unique letters (z, w, u, x, g) identify digits directly.
• Order ensures dependencies resolve (e.g., "three" after "eight" for 'h').
• Single pass with constant space (26 letters).

Step-by-Step Example

Example: s = "eighthree"

• Count: e:3, i:1, g:1, h:2, t:1, r:1.
• Decode:
• 'g' → "eight" (8): e,i,g,h,t, count -= 1 each, e:2, i:0, g:0, h:1, t:0, r:1, digits = [8].
• 'h' → "three" (3): t,h,r,e,e, count -= 1 each, e:0, h:0, r:0, digits = [8, 3].
• Result: Sort [8, 3] → "38".

Example: s = "owoztneoer"

• Count: o:2, w:1, z:1, t:1, n:1, e:2, r:1.
• Decode:
• 'z' → "zero" (0): z,e,r,o, o:1, w:1, t:1, n:1, e:1, digits = [0].
• 'w' → "two" (2): t,w,o, o:0, n:1, e:1, digits = [0, 2].
• 'n' → "one" (1): o,n,e, all 0, digits = [0, 2, 1].
• Result: "012".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def originalDigits(self, s: str) -> str:
        # Step 1: Count letters
        count = [0] * 26
        for char in s:
            count[ord(char) - ord('a')] += 1

        # Step 2: Decode digits using unique letters
        digits = [0] * 10

        # Zero (z unique)
        digits[0] = count[ord('z') - ord('a')]
        count[ord('z') - ord('a')] -= digits[0]
        count[ord('e') - ord('a')] -= digits[0]
        count[ord('r') - ord('a')] -= digits[0]
        count[ord('o') - ord('a')] -= digits[0]

        # Two (w unique)
        digits[2] = count[ord('w') - ord('a')]
        count[ord('t') - ord('a')] -= digits[2]
        count[ord('w') - ord('a')] -= digits[2]
        count[ord('o') - ord('a')] -= digits[2]

        # Four (u unique)
        digits[4] = count[ord('u') - ord('a')]
        count[ord('f') - ord('a')] -= digits[4]
        count[ord('o') - ord('a')] -= digits[4]
        count[ord('u') - ord('a')] -= digits[4]
        count[ord('r') - ord('a')] -= digits[4]

        # Six (x unique)
        digits[6] = count[ord('x') - ord('a')]
        count[ord('s') - ord('a')] -= digits[6]
        count[ord('i') - ord('a')] -= digits[6]
        count[ord('x') - ord('a')] -= digits[6]

        # Eight (g unique)
        digits[8] = count[ord('g') - ord('a')]
        count[ord('e') - ord('a')] -= digits[8]
        count[ord('i') - ord('a')] -= digits[8]
        count[ord('g') - ord('a')] -= digits[8]
        count[ord('h') - ord('a')] -= digits[8]
        count[ord('t') - ord('a')] -= digits[8]

        # Three (h after eight)
        digits[3] = count[ord('h') - ord('a')]
        count[ord('t') - ord('a')] -= digits[3]
        count[ord('h') - ord('a')] -= digits[3]
        count[ord('r') - ord('a')] -= digits[3]
        count[ord('e') - ord('a')] -= digits[3] * 2

        # Five (f after four)
        digits[5] = count[ord('f') - ord('a')]
        count[ord('f') - ord('a')] -= digits[5]
        count[ord('i') - ord('a')] -= digits[5]
        count[ord('v') - ord('a')] -= digits[5]
        count[ord('e') - ord('a')] -= digits[5]

        # Seven (s after six)
        digits[7] = count[ord('s') - ord('a')]
        count[ord('s') - ord('a')] -= digits[7]
        count[ord('e') - ord('a')] -= digits[7] * 2
        count[ord('v') - ord('a')] -= digits[7]
        count[ord('n') - ord('a')] -= digits[7]

        # Nine (i after five, six, eight)
        digits[9] = count[ord('i') - ord('a')]
        count[ord('n') - ord('a')] -= digits[9] * 2
        count[ord('i') - ord('a')] -= digits[9]
        count[ord('e') - ord('a')] -= digits[9]

        # One (n after nine, seven, one)
        digits[1] = count[ord('n') - ord('a')]

        # Step 3: Build result
        result = ""
        for i in range(10):
            result += str(i) * digits[i]

        return result

• Line 4-6: Count letters:
• Array for 'a' to 'z', increment per char (e.g., 'e' → count[4] += 1).
• Line 9-57: Decode digits:
• Line 11-15: "zero" via 'z', subtract z,e,r,o.
• Line 18-22: "two" via 'w', subtract t,w,o.
• Line 25-30: "four" via 'u', subtract f,o,u,r.
• Line 33-38: "six" via 'x', subtract s,i,x.
• Line 41-47: "eight" via 'g', subtract e,i,g,h,t.
• Line 50-55: "three" via 'h' (post-8), subtract t,h,r,e,e.
• Line 58-63: "five" via 'f' (post-4), subtract f,i,v,e.
• Line 66-71: "seven" via 's' (post-6), subtract s,e,v,e,n.
• Line 74-79: "nine" via 'i' (post-5,6,8), subtract n,i,n,e.
• Line 82: "one" via 'n' (post-9,7), n,o,e already subtracted.
• Line 85-87: Build result:
• Append each digit by its count (e.g., "0" * 1 + "1" * 1).
• Time Complexity: O(n)—one pass to count, constant steps.
• Space Complexity: O(1)—fixed-size arrays (26 and 10).

This is like cracking a word puzzle with a clever clue order!

Alternative Solution: Brute Force with Permutations (Conceptual)

Why an Alternative Approach?

The brute force with permutations method tries all possible digit combinations to match the letter count, then picks the smallest valid string. It’s O(n! * n) time and O(n) space—intuitive but impractical for large inputs. It’s like guessing every possible number combo until the letters fit!

How It Works (Simplified)

Picture it as a guess-and-check game:

• Step 1: Count letters in s.
• Step 2: Generate digit combos (0-9), check letter counts.
• Step 3: Return smallest valid string.

Step-by-Step Example (Conceptual)

Example: s = "eighthree"

• Count: e:3, i:1, g:1, h:2, t:1, r:1.
• Try: "38" → "threeeight" matches count, ✓.
• Result: "38".

Code for Brute Force (Simplified, Not Full)

Copy codeclass Solution:
    def originalDigits(self, s: str) -> str:
        # Digit words
        digit_words = ["zero", "one", "two", "three", "four", 
                      "five", "six", "seven", "eight", "nine"]

        # Count letters in s
        count = [0] * 26
        for char in s:
            count[ord(char) - ord('a')] += 1

        def check_combo(combo):
            temp = [0] * 26
            for digit in combo:
                for c in digit_words[int(digit)]:
                    temp[ord(c) - ord('a')] += 1
            return temp == count

        # Simplified brute force (not full permutations)
        min_result = None
        for i in range(10):
            for j in range(i, 10):
                combo = str(i) + str(j)
                if check_combo(combo):
                    if min_result is None or combo < min_result:
                        min_result = combo

        return min_result if min_result else ""

# Note: Full brute force would use itertools.permutations, too slow.

• Time Complexity: O(n! * n)—permutations explode.
• Space Complexity: O(n)—temp arrays.

It’s a slow guesser!

Comparing the Two Solutions

• Greedy with Counting (Best):
• Pros: O(n), O(1), fast and clever.
• Cons: Order logic to grasp.
• Brute Force (Alternative):
• Pros: O(n! * n), O(n), intuitive.
• Cons: Impractical.

Greedy wins for speed.

Additional Examples and Edge Cases

• "zero": "0".
• "twotwo": "22".
• "nineeight": "89".

Greedy handles all.

Complexity Breakdown

• Greedy: Time O(n), Space O(1).
• Brute Force: Time O(n! * n), Space O(n).

Greedy’s the champ.

Key Takeaways

• Greedy: Clue it out!
• Brute Force: Guess it all!
• Digits: Letters unlock.
• Python Tip: Counts rock—see [Python Basics](/python/basics).

Final Thoughts: Crack That Code

LeetCode 423: Reconstruct Original Digits from English in Python is a letter-decoding adventure. Greedy with counting cracks it fast, while brute force grinds it slow. Want more string fun? Try LeetCode 415: Add Strings or LeetCode 767: Reorganize String. Ready to decode? Head to Solve LeetCode 423 on LeetCode and reconstruct those digits today!