Shuffle String: domanda di esempio UnStop

Dichiarazione problema

Al signor Agoji viene data una stringa mescolata creata mescolando casualmente una stringa speciale. Una puntura sarà chiamata speciale solo se è formata unendo alcune parole speciali un numero qualsiasi di volte. Le parole speciali sono la mappatura dei numeri (0 <= numero <10) alle loro parole, ad esempio, la mappatura di '0' a 'zero', la mappatura di '1' a 'uno' e così via. Al signor Agoji viene chiesto di convertire la stringa mescolata nel numero speciale più piccolo. Un numero speciale è un numero formato utilizzando numeri (0 <= numero < 10) senza zeri iniziali. Il signor Agoji non essendo così bravo con i numeri e le stringhe chiede il tuo aiuto.

Formato di input

La prima riga dell'input conterrà T, il numero di test case, 1 <= T <= 100 Per ogni test case, ci sarà una, s stringa mescolata, su una riga separata

1 <= s.lunghezza <= 100000

Formato di output

Per ogni caso di test, sulla nuova riga, il numero speciale più piccolo è nel formato stringa. Alcune note sull'output: la stringa mescolata sarà sempre in grado di convertire in almeno una stringa speciale valida. La stringa mescolata conterrà solo piccoli alfabeti inglesi. Se una stringa mescolata contiene solo zeri, dovresti emettere "0".

Approccio:

1. creare una mappa da cifre a parole
2. crea una mappa di frequenza dei caratteri dalla stringa di input
3. Attraversa tutte le cifre da 0 a 9 e vedi quanti numeri sono rappresentati nella stringa. salvalo nel dizionario digit_freq
4. ordina tutti i numeri in digit_freq e crea una stringa da quello
5. Ci sono pochi casi limite di cui dobbiamo occuparci. Se tutti sono zero, allora restituisci 0. Un altro caso limite è che non possiamo mantenere 0 nelle prime posizioni della stringa di risultato. possiamo mantenere tutti zeri dopo la prima cifra diversa da zero per creare il numero più piccolo in base alle esigenze.

def smallest_special_number(string):
    num_to_word = {
        '0' : 'zero', 
        '1' : 'one', 
        '2' : 'two',  
        '3' : 'three', 
        '4' : 'four', 
        '5' : 'five', 
        '6' : 'six', 
        '7' : 'seven', 
        '8' : 'eight', 
        '9' : 'nine',
    }

    char_freq = {}
    for char in string:
        if char not in char_freq:
            char_freq[char] = 1
        else:
            char_freq[char] += 1
    
    digit_freq = {}
    for digit in num_to_word:
        word = num_to_word[digit]
        count = char_freq.get(word[0], 0)
        for char in word[1:]:
            count = min(count, char_freq.get(char, 0))
        digit_freq[digit] = count
    result = ''
    for num in sorted(digit_freq.keys()):
        result += num * digit_freq[num]
    
    # Handle special cases
    if len(result) == 0:
        return '0'
    if result[0] == '0':
        zeros = 1
        for i in range(1, len(result)):
            if result[i] == '0':
                zeros += 1
            else:
                break
    if zeros == len(result):
        return '0'
    if zeros != 0:
        result = result[i] + '0' * zeros + result[i+1:]
    return result



# Read input and process test cases
s = "ewtooetzrowon"
print(smallest_special_number(s))

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        scanner.nextLine();
        while (t-- > 0) {
            String s = scanner.nextLine();
            String result = smallestSpecialNumber(s);
            System.out.println(result);
        }
        scanner.close();
    }

    public static String smallestSpecialNumber(String string) {
        Map<Character, String> numToWord = new HashMap<Character, String>() {{
            put('0', "zero");
            put('1', "one");
            put('2', "two");
            put('3', "three");
            put('4', "four");
            put('5', "five");
            put('6', "six");
            put('7', "seven");
            put('8', "eight");
            put('9', "nine");
        }};

        Map<Character, Integer> charFreq = new HashMap<>();
        for (char c : string.toCharArray()) {
            charFreq.put(c, charFreq.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> digitFreq = new HashMap<>();
        for (char digit : numToWord.keySet()) {
            String word = numToWord.get(digit);
            int count = charFreq.getOrDefault(word.charAt(0), 0);
            for (int i = 1; i < word.length(); i++) {
                count = Math.min(count, charFreq.getOrDefault(word.charAt(i), 0));
            }
            digitFreq.put(digit, count);
        }

        StringBuilder sb = new StringBuilder();
        for (char digit = '0'; digit <= '9'; digit++) {
            int freq = digitFreq.getOrDefault(digit, 0);
            sb.append(String.valueOf(digit).repeat(freq));
        }
        String result = sb.toString();

        // Handle special cases
        if (result.length() == 0) {
            return "0";
        }
        if (result.charAt(0) == '0') {
            int zeros = 1;
            int i = 1;
            for (; i < result.length(); i++) {
                if (result.charAt(i) == '0') {
                    zeros++;
                } else {
                    break;
                }
            }
            if (zeros == result.length()) {
                return "0";
            }
            result = result.charAt(i) + "0".repeat(zeros) + result.substring(i + 1);
        }
        return result;
    }
}

Per favore seguimi su Medium e Youtube se hai trovato utile questa spiegazione.

Aiuta l'algoritmo a trovare questo articolo ad altri utenti facendo clic su clap. :)