Ordnen Sie die Zeichen einer Zeichenfolge neu an, um eine gültige englische numerische Darstellung zu erhalten

In diesem Problem müssen wir die Zeichen der gegebenen Zeichenfolge neu anordnen, um eine gültige englische numerische Darstellung zu erhalten. Der erste Ansatz könnte darin bestehen, alle Permutationen der Zeichenfolge zu finden, englische Wörter mit Bezug zu Zahlen zu extrahieren und sie in Zahlen umzuwandeln.

Eine andere Möglichkeit, dieses Problem zu lösen, besteht darin, aus jedem Wort ein eindeutiges Zeichen zu finden. In diesem Tutorial lernen wir zwei Möglichkeiten kennen, ein bestimmtes Problem zu lösen.

Problemstellung- Wir erhalten eine Zeichenfolge der Länge N, die Kleinbuchstaben enthält. Die Zeichenfolge enthält englische Wortdarstellungen der Zahlen [0–9] in zufälliger Reihenfolge. Wir müssen englische Wörter aus Zeichenfolgen extrahieren, sie in Zahlen umwandeln und diese Zahlen in aufsteigender Reihenfolge anzeigen

Beispiel Beispiel

Eingabe – str = "zeoroenwot"

Ausgabe –‘012’

Erklärung– Wir können „Null“, „Eins“ und „Zwei“ aus der gegebenen Zeichenfolge extrahieren und sie dann in aufsteigender numerischer Reihenfolge sortieren.

Eingabe – str = ‚zoertowxisesevn‘

Ausgabe –‘0267’

Erklärung – Wir können „null“, „zwei“, „sechs“ und „sieben“ aus der gegebenen Zeichenfolge extrahieren.

Methode 1

In dieser Methode verwenden wir die Methode next_permutation(), um die Permutation der Zeichenfolge zu erhalten. Anschließend extrahieren wir zahlenbezogene englische Wörter aus jeder Permutation und verfolgen die maximale Gesamtzahl der aus jeder Permutation extrahierten Wörter. Daraus bilden wir die Zeichenfolge.

Algorithmus

• Definieren Sie die Funktion countOccurrences(), die Zeichenfolgen und Wörter als Parameter akzeptiert. Es wird verwendet, um die Häufigkeit des Vorkommens eines bestimmten Worts in einer bestimmten Zeichenfolge zu zählen.

• Definieren Sie die Variable „count“ und initialisieren Sie sie auf Null.

• Verwenden Sie eine While-Schleife, um die Zeichenfolge zu durchlaufen. Wenn wir das Wort an der aktuellen Position finden, wird der Wert von „count“ um 1 erhöht und der Wert von „pos“ um die Länge des Wortes übersprungen.

• Gibt den Wert von „count“ zurück

Die Funktion „convertToDigits()“ wird verwendet, um Wörter in Zahlen umzuwandeln

• Definieren Sie einen Vektor mit dem Namen „Wörter“, der die englische Darstellung von Zahlen enthält. Definieren Sie außerdem „max_digits“, um die maximale Anzahl von Wörtern in jeder Permutation der Zeichenfolge zu speichern. Definieren Sie außerdem die Karte „digit_freq“, um die Häufigkeit jeder Ziffer zu speichern, wenn wir aus jeder Permutation das maximale Wort extrahieren können.

• Verwenden Sie die Methode sort(), um die angegebene Zeichenfolge zu sortieren.

• Verwenden Sie die Methode next_permutations() mit der Schleife do-while(). Verwenden Sie innerhalb der Schleife eine weitere Schleife, um die Wortvektoren zu durchlaufen.

• Zählen Sie die Vorkommen jedes Wortes in der aktuellen Permutation und aktualisieren Sie die Karte „word_freq“ auf dieser Grundlage. Fügen Sie gleichzeitig den resultierenden Wert zur Variablen „cnt“ hinzu.

• Wenn der Wert von „cnt“ größer als „max_digits“ ist, aktualisieren Sie die Werte von „max_digits“ und „digit_frequancy“.

• Durchlaufen Sie die Karte „digit_freq“ und konvertieren Sie Zahlen in Zeichenfolgen.

• Beispiel

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

Ausgabe

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

Zeitliche Komplexität – O(N*N!), weil wir alle Permutationen finden müssen.

Raumkomplexität – O(N) zum Speichern der endgültigen Zeichenfolge.

Methode 2

Diese Methode ist eine optimierte Version der oben genannten Methode. Hier nehmen wir aus jedem Wort ein eindeutiges Zeichen und finden anhand dieses Zeichens das genaue Wort aus der angegebenen Zeichenfolge.

Beobachten

Wir haben „z“ eindeutige Einsen in „Null“.

• Wir haben „w“ einzigartige in „zwei“.

• Wir haben „u“-Einzigartige in „vier“.

• Wir haben „x“ einzigartige von „sechs“.

• Wir haben „gg“-Einzelstücke in „acht“.

• Wir können alle eindeutigen Wörter, die „h“ enthalten, aus „drei“ extrahieren, genau wie wir oben betrachtet haben.

• Wir können das einzige „o“ aus „one“ herausnehmen, weil wir alle Wörter berücksichtigt haben, die „o“ enthalten.

• Wir können „f“ aus „fünf“ als alle Wörter auswählen, die wie oben „f“ enthalten.

• Wir haben „v“ einzigartige in „sieben“.

• Wir können das „i“ von „nine“ als alle Wörter nehmen, die „i“ enthalten und die wir oben betrachtet haben.

• Algorithmus

Definieren Sie den Vektor „Wörter“, der englische Wörter enthält, und achten Sie darauf, die untenstehende Beispielreihenfolge einzuhalten, da wir eindeutige Wörter entsprechend berücksichtigt haben. Definieren Sie außerdem einen Vektor eindeutiger Zeichen und deren numerische Darstellung

• Zählen Sie die Häufigkeit jedes Zeichens und speichern Sie sie in der Karte.

• Durchsuchen Sie eine Reihe einzigartiger Charaktere

• Wenn die Karte ein derzeit eindeutiges Zeichen enthält, speichern Sie seinen Häufigkeitswert in der Variablen „cnt“.

• Jetzt iterieren Sie über das aktuelle Wort. Verringern Sie die Häufigkeit jedes Zeichens eines Wortes um „cnt“ in der Karte.

• 在‘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)，用于存储最终的字符串。

Das obige ist der detaillierte Inhalt vonOrdnen Sie die Zeichen einer Zeichenfolge neu an, um eine gültige englische numerische Darstellung zu erhalten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!