[leetcode problem solving report] 423 Rebuild numbers from English

One 、 subject

1. Title Description

423. Reconstructing Chinese from English

difficulty ： secondary

Give you a string s , It contains a number of numbers represented by English words in disordered alphabetical order （0-9）. Press Ascending Returns the original number .

Example 1：

 Input ：s = "owoztneoer"
 Output ："012"

Example 2：

 Input ：s = "fviefuro"
 Output ："45"

Tips ：

• 1 <= s.length <= 105
• s[i] by [“e”,“g”,“f”,“i”,“h”,“o”,“n”,“s”,“r”,“u”,“t”,“w”,“v”,“x”,“z”] One of these characters
• s The guarantee is a string that meets the requirements of the topic

2. Original link

link : 423. Reconstructing Chinese from English

Two 、 Problem solving report

1. Thought analysis

  An interesting question , Just got it, there will be no idea .
  I have reserved some useless notes for this question , But this part reflects my thinking process .

• The title is guaranteed to be a legal string , First of all, I will think of counting the number of occurrences of each character, and then dfs Enumerate every word to try . Looked at the eye data range 1e5 Obviously not .
• Even if it's dfs Enumerating each word also counts each word , The number of occurrences of each character .
• Is it meaningful to count the length of each word ？ It seems useless .
• Then new ideas appeared ： Does a character exist in only one word , such as z, Only in zero(0) in , that s in z The number of times is zero Number of occurrences ！
• Therefore, the most important statistics in my notes appear ： Calculate which words each character appears in , And sort by the number of times , It turns out like this ：
• [('z', {0}), ('w', {2}), ('u', {4}), ('x', {6}), ('g', {8}), ('h', {8, 3}), ('f', {4, 5}), ('v', {5, 7}), ('s', {6, 7}), ('r', {0, 3, 4}), ('n', {1, 9, 7}), ('t', {8, 2, 3}), ('o', {0, 1, 2, 4}), ('i', {8, 9, 5, 6}), ('e', {0, 1, 3, 5, 7, 8, 9})]
• Not very good. , Let me type a watch ：

• With this watch , We found that z w u x g, It only appears in a certain word , Then in the string s Count the number of occurrences of these characters in , It is equal to the number of times their corresponding words appear .
• this 5 The two words are z:0,w:2,u:4,x:6,g:8.
• What about the rest , Let's continue to look down on this table ,h This line ,h Only in 8 and 3 in . and 8 We can know the quantity of , be equal to g Number of occurrences , Then I just need to deal with it in advance g, hold 8 Subtract the corresponding number from all the corresponding characters ( signify s Does not exist in the 8 了 ), Equate to h Can only appear in 3 in , that h You can also find it .
• Similarly, continue to process downward , All the time v No problem . Last one left 1 and 9 Out-of-service n To represent the , Because they appear at the same time n in , Keep looking backwards , Find out i In addition to 1 It's all dealt with , Then use i To represent the 1, There's one left i To represent the 9.
• Just type this watch . The rest is coding .
• In fact, it uses Counter Even trouble , There is no preprocessing subtraction in the official solution , When updating the answer directly, subtract , Faster .

2. Complexity analysis

Worst time complexity O(n×10),n yes s The length of ,10 It's a total of 10 Word , The maximum word length is 5, Ignore this constant .

3. Code implementation

The meter .

words = [
            'zero','one','two','three','four',
            'five','six','seven','eight','nine'
        ]
cnts = [Counter(w) for w in words]
# lens = defaultdict(list)
# for w in words:
# lens[len(w)].append(w)

# c_times = defaultdict(set)
# for i,w in enumerate(words):
# for c in w:
# c_times[c].add(i)
# c_times_list = sorted(c_times.items(),key = lambda x:len(x[1]))
# print(c_times_list)
orders = [
    ('z',0),
    ('w',2),
    ('u',4),
    ('x',6),
    ('g',8),
    ('h',3),
    ('f',5),
    ('v',7),
    ('o',1),
    ('i',9)
]
class Solution:
    def originalDigits(self, s: str) -> str:       
        cs = Counter(s)
        ans = [0] * 10       
        for c,n in orders:
            # print(cs)
            ans[n] = cs[c]
            for _ in range(ans[n]):
                cs -= cnts[n]
        # print(ans)
        ret = []
        for i,v in enumerate(ans):
            ret.extend([i]*v)
        return ''.join(map(str,ret))                   

3、 ... and 、 Summary of this topic

1. Brain teaser problems need to be studied for a while .