How do you solve Reconstruct Original Digits from English on LeetCode?

Reconstruct Original Digits from English (LeetCode #423) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Unique letters in digit words can be leveraged to identify digits directly.

What is the brute force solution for Reconstruct Original Digits from English?

The brute force approach for Reconstruct Original Digits from English is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves generating all possible combinations of digits and checking if they can be formed from the given string. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Reconstruct Original Digits from English?

Reconstruct Original Digits from English uses the following concepts: Hash Table, Math, String. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Reconstruct Original Digits from English?

Think about how unique characters can help simplify the problem. Practice counting frequencies and using them to derive results. Always consider edge cases and constraints given in the problem.

What are common mistakes when solving Reconstruct Original Digits from English?

Failing to account for all unique letters when determining digit counts. Not using character frequency efficiently, leading to unnecessary checks.

#423

Reconstruct Original Digits from English

Medium

Hash TableMathStringHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution leverages the unique letters in the English words for digits to count occurrences and derive the digits directly. This is efficient and avoids unnecessary checks.

⚙️

Algorithm

4 steps

1Step 1: Count the frequency of each character in the input string.
2Step 2: Use the unique characters of certain digits to determine how many of each digit can be formed.
3Step 3: Subtract the counts of characters used for each digit from the frequency map.
4Step 4: Collect the digits in ascending order based on their counts.

solution.py16 lines

1from collections import Counter
2
3def originalDigits(s):
4    count = Counter(s)
5    result = [0] * 10
6    result[0] = count['z']  # zero
7    result[2] = count['w']  # two
8    result[4] = count['u']  # four
9    result[6] = count['x']  # six
10    result[5] = count['f'] - result[4]  # five
11    result[7] = count['s'] - result[6]  # seven
12    result[8] = count['g']  # eight
13    result[3] = count['h'] - result[8]  # three
14    result[1] = count['o'] - result[0] - result[2] - result[4]  # one
15    result[9] = count['i'] - result[5] - result[6] - result[8]  # nine
16    return ''.join(str(i) * result[i] for i in range(10))

ℹ

Complexity note: The time complexity is O(n) because we only iterate through the string once to count characters, and the space complexity is O(1) since we use a fixed-size array for counts.

1Unique letters in digit words can be leveraged to identify digits directly.
2Counting character frequencies allows for efficient digit reconstruction.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.