Réorganiser les caractères d'une chaîne pour former une représentation numérique anglaise valide

Dans ce problème, nous devons réorganiser les caractères de la chaîne donnée pour obtenir une représentation numérique anglaise valide. La première approche pourrait consister à trouver toutes les permutations de la chaîne, à extraire les mots anglais liés aux nombres et à les convertir en nombres.

Une autre façon de résoudre ce problème est de trouver un caractère unique dans chaque mot. Dans ce tutoriel, nous allons apprendre deux manières de résoudre un problème donné.

Énoncé du problème- On nous donne une chaîne de longueur N contenant des caractères minuscules. La chaîne contient des représentations de mots anglais de nombres [0-9] dans un ordre aléatoire. Nous devons extraire les mots anglais des chaînes, les convertir en nombres et afficher ces nombres par ordre croissant

Exemple Exemple

Entrée – str = "zeoroenwot"

Sortie –« 012 »

Explication– Nous pouvons extraire « zéro », « un » et « deux » de la chaîne donnée, puis les trier par ordre numérique croissant.

Entrée – str = 'zoertowxisesevn'

Sortie –« 0267 »

Explication – Nous pouvons extraire « zéro », « deux », « six » et « sept » de la chaîne donnée.

Méthode 1

Dans cette méthode, nous utiliserons la méthode next_permutation() pour obtenir la permutation de la chaîne. Nous extrairons ensuite les mots anglais liés aux nombres de chaque permutation et garderons une trace du nombre total maximum de mots extraits de toute permutation. À partir de là, nous formerons la chaîne.

Algorithme

• Définissez la fonction countOccurrences(), qui accepte les chaînes et les mots comme paramètres. Il est utilisé pour compter les occurrences d'un mot spécifique dans une chaîne donnée.

• Définissez la variable 'count' et initialisez-la à zéro.

• Utilisez une boucle while pour parcourir la chaîne. Si nous trouvons le mot à la position actuelle, la valeur de « count » est augmentée de 1 et la valeur de « pos » est ignorée de la longueur du mot.

• Renvoyer la valeur de « count »

La fonction

• convertToDigits() est utilisée pour convertir des mots en nombres

• Définissez un vecteur nommé « mots », qui contient la représentation anglaise des nombres. Définissez également « max_digits » pour stocker le nombre maximum de mots dans toute permutation de la chaîne. De plus, définissez la carte 'digit_freq' pour stocker la fréquence de chaque chiffre lorsque nous pouvons extraire le maximum de mots de n'importe quelle permutation.

• Utilisez la méthode sort() pour trier la chaîne donnée.

• Utilisez la méthode next_permutations() avec la boucle do-while(). Dans la boucle, utilisez une autre boucle pour parcourir les vecteurs de mots.

• Comptez les occurrences de chaque mot dans la permutation actuelle et mettez à jour la carte 'word_freq' en fonction de cela. En même temps, ajoutez la valeur résultante à la variable 'cnt'.

• Si la valeur de « cnt » est supérieure à « max_digits », mettez à jour les valeurs de « max_digits » et « digit_frequancy ».

• Parcourez la carte "digit_freq" et convertissez les nombres en chaînes.

Exemple

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

//  function to count the total number of occurrences of a word in a string
int countOccurrences(const string &text, const string &word){
   int count = 0;
   size_t pos = 0;
   while ((pos = text.find(word, pos)) != std::string::npos){
      count++;
      pos += word.length();
   }
   return count;
}
string convertToDigits(string str){
   // defining the words vector
   vector<string> words = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
   int max_digits = 0;
   map<int, int> digit_freq;
   // Traverse the permutations vector
   sort(str.begin(), str.end()); // Sort the string in non-decreasing order
   do{
      string temp = str;
      int cnt = 0;
      map<int, int> word_freq;
      // Traverse the words vector
      for (int j = 0; j < words.size(); j++){
         string temp_word = words[j];
         // finding the number of occurrences of the word in the permutation
         int total_temp_words = countOccurrences(temp, temp_word);
         // storing the number of occurrences of the word in the map
         word_freq[j] = total_temp_words;
         cnt += total_temp_words;
     }
     // If the total number of digits in the permutation is greater than the max_digits, update the max_digits and digit_freq
     if (cnt > max_digits){
         max_digits = cnt;
         digit_freq = word_freq;
      }
   } while (next_permutation(str.begin(), str.end()));
   string res = "";
   // Traverse the digit_freq map
   for (auto it = digit_freq.begin(); it != digit_freq.end(); it++){
      int digit = it->first;
      int freq = it->second;
      // Append the digit to the result string
      for (int i = 0; i < freq; i++){
         res += to_string(digit);
      }
   }
   return res;
}
int main(){
   string str = "zeoroenwot";
   // Function Call
   cout << "The string after converting to digits and sorting them in non-decreasing order is " << convertToDigits(str);
}

Sortie

The string after converting to digits and sorting them in non-decreasing order is 012

Complexité temporelle - O(N*N !), car nous devons trouver toutes les permutations.

Complexité spatiale - O(N) pour stocker la chaîne finale.

Méthode 2

Cette méthode est une version optimisée de la méthode ci-dessus. Ici, nous prendrons un caractère unique de chaque mot et trouverons le mot exact de la chaîne donnée en fonction de ce caractère.

Observer

• Nous avons des « z » uniques en « zéro ».

• Nous avons des « w » uniques sur « deux ».

• Nous en avons des « u » uniques sur « quatre ».

• Nous en avons « x » uniques sur « six ».

• Nous en avons des « gg » uniques en « huit ».

• Nous pouvons extraire tous les mots uniques contenant « h » de « trois », tout comme nous l'avons considéré ci-dessus.

• Nous pouvons supprimer le seul « o » de « un » car nous avons considéré tous les mots contenant « o ».

• Nous pouvons sélectionner « f » parmi « cinq » comme tous les mots contenant « f » comme ci-dessus.

• Nous avons des « v » uniques dans « sept ».

• Nous pouvons prendre le « i » de « neuf » comme tous les mots contenant « i » que nous avons considérés ci-dessus.

Algorithme

• Définissez le vecteur « mots » contenant des mots anglais et assurez-vous de suivre l'ordre des exemples ci-dessous car nous avons considéré des mots uniques en conséquence. Définissez également un vecteur de caractères uniques et leur représentation numérique

• Comptez la fréquence de chaque personnage et stockez-la dans la carte.

• Parcourez un éventail de personnages uniques

• Si la carte contient un caractère actuellement unique, stockez sa valeur de fréquence dans la variable 'cnt'.

• Maintenant, parcourez le mot actuel. Diminuez la fréquence de chaque caractère d'un mot de 'cnt' dans la carte.

• 在‘digits’向量中添加一个单词，重复‘cnt’次。

• 对数字字符串进行排序，并从函数中返回。

示例

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

string convertToDigits(string str){
   // store the words corresponding to digits
   vector<string> words = { "zero", "two", "four", "six", "eight", "three", "one", "five", "seven", "nine" };
   // store the unique characters of the words
   vector<char> unique_chars = {'z',  'w', 'u', 'x', 'g', 'h', 'o', 'f', 'v', 'i'};
   // store the digits corresponding to the words
   vector<int> numeric = {0, 2, 4, 6, 8, 3, 1, 5, 7, 9};
   // to store the answer
   vector<int> digits = {};
   // unordered map to store the frequency of characters
   unordered_map<char, int> freq;
   // count the frequency of each character
   for (int i = 0; i < str.length(); i++){
      freq[str[i]]++;
   }
   // Iterate over the unique characters
   for (int i = 0; i < unique_chars.size(); i++){
      // store the count of the current unique character
      int cnt = 0;
      // If the current unique character is present, store its count. Otherwise, it will be 0.
      if (freq[unique_chars[i]] != 0)
          cnt = freq[unique_chars[i]];
      // Iterate over the characters of the current word
      for (int j = 0; j < words[i].length(); j++){
          // Reduce the frequency of the current character by cnt times in the map
          if (freq[words[i][j]] != 0)
             freq[words[i][j]] -= cnt;
      }
      // Push the current digit cnt times in the answer
      for (int j = 0; j < cnt; j++)
         digits.push_back(numeric[i]);
   }
   // sort the digits in non-decreasing order
   sort(digits.begin(), digits.end());
   string finalStr = "";
   // store the answer in a string
   for (int i = 0; i < digits.size(); i++)
     finalStr += to_string(digits[i]);      
   return finalStr;
}
int main(){
   string str = "zoertowxisesevn";
   // Function Call
   cout << "The string after converting to digits and sorting them in non-decreasing order is " << convertToDigits(str);
}

输出

The string after converting to digits and sorting them in non-decreasing order is 0267

时间复杂度 - O(N)，其中N是字符串的长度。

空间复杂度 - O(N)，用于存储最终的字符串。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!