How to solve the problem of combining numbers by prefix?

Question

Mathematics

The essence of the problem:
There is a random list of phone number prefixes, i.e. numbers in the range from 1 to 99 999 999 999 (maximum length 11 characters), presented as a string.
It is necessary to reduce the numbers in this list to the largest prefix, namely:
- for example, if the list contains prefixes 123 0 , 123 1 , 123 2 ... 123 9 , they are removed and the prefix 123 is added instead;
- then the cycle repeats - if there are prefixes 12 0 , 12 1 , 12 2 , 123 ... 12 9 in the list , they are combined to 12.
- and so on until all elements of the list combine to the largest prefix.
- prefixes starting with 0 do not need to be combined.
Poke, please, into the algorithm for solving this problem. I see that it’s like enumeration and recursion, but I don’t understand from which end to start.

Answer 1

Look towards Radix Sort. You can stop at the stage when the digit of the number by which you want to sort is selected. Or start sorting from the highest digits. And when there is a distribution among baskets (buckets), we will get numbers with the same prefix. Alternatively, you can try this way.

Answer 2

Unclear. If the list contains the number 123 and the entire block 1230, 1231, ... 1239, what will happen after replacing the block with a prefix? Two numbers 123?
And if 123 has already turned out, how is the common prefix of 5-digit numbers?
And by the way, the description says what to do when there are already prefixes in the list. And where does the first prefix come from when there are only numbers?
If I understand correctly, this is how it should be done.
1) sort the numbers by length, and within each length - in ascending order.
2) look at the numbers in order. If there is a number ending in one or more zeros, then we check whether it is the beginning of a block with a common prefix (by looking at subsequent numbers before the first failure). In this case, for a number ending in one zero, the block can have a length of 10; for a number ending in two zeros - 10 or 100, etc. We replace the longest of the detected blocks with a prefix.
Everything. No enumeration and no recursion, just sorting and linear browsing.