Shuffle String - Exemple de question UnStop

Énoncé du problème

M. Agoji reçoit une chaîne mélangée faite en mélangeant au hasard une chaîne spéciale. Une piqûre ne sera appelée spéciale que si elle est formée en joignant des mots spéciaux un certain nombre de fois. Les mots spéciaux sont le mappage de nombres (0 <= nombre < 10) à leurs mots, par exemple, le mappage de '0' à 'zéro', le mappage de '1' à 'un', etc. M. Agoji est invité à convertir la chaîne mélangée au plus petit nombre spécial. Un nombre spécial est un nombre formé à l'aide de nombres (0 <= nombre < 10) sans aucun zéro non significatif. M. Agoji n'étant pas si doué avec les chiffres et les chaînes demande votre aide.

Format d'entrée

La première ligne de l'entrée contiendra T, le nombre de cas de test, 1 <= T <= 100 Pour chaque cas de test, Il y aura une, s chaîne mélangée, sur une ligne séparée

1 <= s.length <= 100000

Format de sortie

Pour chaque cas de test, sur la nouvelle ligne, le plus petit nombre spécial est au format chaîne. Quelques notes sur la sortie : la chaîne mélangée pourra toujours être convertie en au moins une chaîne spéciale valide. La chaîne mélangée ne contiendra que de petits alphabets anglais. Si une chaîne mélangée ne contient que des zéros, vous devez afficher « 0 ».

Approche:

1. créer une carte des chiffres aux mots
2. créer une carte de fréquence des caractères à partir de la chaîne d'entrée
3. Parcourez tous les chiffres de 0 à 9 et voyez combien de nombres sont représentés dans la chaîne. enregistrez-le dans le dictionnaire digit_freq
4. trier tous les nombres dans digit_freq et créer une chaîne à partir de cela
5. Il y a peu de cas extrêmes dont nous devons prendre soin. Si tous sont nuls, renvoyez 0. Un autre cas limite est que nous ne pouvons pas conserver 0 en position avant de la chaîne de résultat. nous pouvons conserver tous les zéros après le premier chiffre non nul pour créer le plus petit nombre selon les besoins.

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;
    }
}

Veuillez me suivre sur Medium et Youtube si vous avez trouvé cette explication utile.

Algorithme d'aide pour trouver cet article aux autres utilisateurs en cliquant sur clap. :)