Sponsored
Sponsored
This approach uses unique identifiers for each digit's word representation in the English language. By identifying letters present in only one digit's name, like 'z' in 'zero', we progressively remove identified digits from the input string. This allows easy recovery of digits based on the frequency of unique letters.
Time Complexity: O(n), where n is the length of the string s, since we iterate over the input string and perform constant-time operations using the Counter.
Space Complexity: O(1), as the count array and resultant digit storage both use fixed space not growing with input size.
1import java.util.*;
2
3public class OriginalDigits {
4 public String originalDigits(String s) {
5 int[] count = new int[26 + (int)'a'];
6 for (char c : s.toCharArray()) {
7 count[c]++;
8 }
9
10 int[] output = new int[10];
11 output[0] = count['z'];
12 output[2] = count['w'];
13 output[4] = count['u'];
14 output[6] = count['x'];
15 output[8] = count['g'];
16
17 output[1] = count['o'] - output[0] - output[2] - output[4];
18 output[3] = count['h'] - output[8];
19 output[5] = count['f'] - output[4];
20 output[7] = count['s'] - output[6];
21 output[9] = count['i'] - output[5] - output[6] - output[8];
22
23 StringBuilder result = new StringBuilder();
24 for (int i = 0; i < 10; i++) {
25 for (int j = 0; j < output[i]; j++) {
26 result.append(i);
27 }
28 }
29 return result.toString();
30 }
31}The Java solution follows an identical logic to the Python version. It counts the frequency of relevant characters using an integer array (sized to map any character index from 'a' to 'z'). Using unique characters, it deduces certain numbers while the combination of others is solved progressively using overlap, in constructing the final digit string.
In this approach, we iteratively subtract recognized digits from the current string until the string is fully reduced. This involves pattern matching for each unique digit using substring searches that account for unique spellings.
Time Complexity: O(n) for analyzing the string and constructing the output.
Space Complexity: O(1) since it uses fixed-size data structures for all computational logic without dynamic extensive allocation.
1#include <stdio.h>
2#include
This C solution proceeds by implementing character frequency counting similar to former strategies. It builds the result string by appending known digits based on zero-indexed character discovery, leveraging array positions for fast access. Memory management is handled manually to construct a resultant char array.