將字串的字元重新排序為有效的英文數字表示

---

在這個問題中，我們需要將給定字串的字元重新排序為有效的英文數字表示。第一種方法可以是查詢字串的所有排列，提取與數字相關的英文單詞，並將它們轉換為數字。

另一種可以用來解決這個問題的方法是，從每個單詞中找到一個唯一的字元。在本教程中，我們將學習解決給定問題的兩種方法。

問題陳述- 我們得到一個包含小寫字元且長度等於N的字串。該字串包含[0-9]數字的英文單詞表示，順序隨機。我們需要從字串中提取英文單詞，將其轉換為數字，並按升序顯示這些數字。

示例

輸入– str = "zeoroenwot"

輸出– ‘012’

解釋– 我們可以從給定的字串中提取“zero”、“one”和“two”，然後我們可以按升序排列數字。

輸入– str = ‘zoertowxisesevn’

輸出– ‘0267’

解釋– 我們可以從給定的字串中提取“zero”、“two”、“six”和“seven”。

方法一

在這種方法中，我們將使用next_permutation()方法來獲取字串的排列。之後，我們將從每個排列中提取與數字相關的英文單詞，並跟蹤從任何排列中提取的最大單詞總數。根據這個總數，我們將形成字串。

演算法

• 定義countOccurrences()函式，該函式以字串和單詞作為引數。它用於計算給定字串中特定單詞的出現次數。

• 定義“count”變數，並將其初始化為零。

• 使用while迴圈遍歷字串。如果我們在當前位置找到該單詞，則將“count”的值增加1，並將“pos”值跳過單詞長度。

• 返回“count”的值。

• convertToDigits()函式用於將單詞轉換為數字。

• 定義名為“words”的向量，其中包含數字的英文表示。還要定義“max_digits”來儲存字串任何排列中的最大單詞數。此外，定義“digit_freq”對映來儲存當我們可以從任何排列中提取最大單詞時每個數字的頻率。

• 使用sort()方法對給定字串進行排序。

• 使用next_permutations()方法和do-while()迴圈。在迴圈中，使用另一個迴圈來迭代單詞向量。

• 計算當前排列中每個單詞的出現次數，並據此更新“word_freq”對映。並將結果值新增到“cnt”變數中。

• 如果“cnt”的值大於“max_digits”，則更新“max_digits”和“digit_frequancy”的值。

• 迭代“digit_freq”對映並將數字轉換為字串。

示例

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

輸出

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

時間複雜度 – O(N*N！)，因為我們需要找到所有排列。

空間複雜度 – O(N)，用於儲存最終字串。

方法二

這種方法是上述方法的最佳化版本。在這裡，我們將從每個單詞中提取一個唯一字元，並根據此字元，我們將從給定字串中找到確切的單詞。

觀察

• “zero”中“z”是唯一的。

• “two”中“w”是唯一的。

• “four”中“u”是唯一的。

• “six”中“x”是唯一的。

• “eight”中“g”是唯一的。

• 我們可以從“three”中取“h”作為唯一字元，因為我們上面已經考慮了所有包含“h”的單詞。

• 我們可以從“one”中取“o”作為唯一字元，因為我們上面已經考慮了所有包含“o”的單詞。

• 我們可以從“five”中取“f”作為唯一字元，因為我們上面已經考慮了所有包含“f”的單詞。

• “seven”中“v”是唯一的。

• 我們可以從“nine”中取“i”作為唯一字元，因為我們上面已經考慮了所有包含“i”的單詞。

演算法

• 定義包含英文單詞的“words”向量，並確保遵循下面示例中給出的順序，因為我們已經相應地考慮了唯一單詞。還要定義唯一字元的向量及其數字表示。

• 計算每個字元的頻率並將其儲存在對映中。

• 遍歷唯一字元陣列。

• 如果對映包含當前唯一字元，則將其頻率值儲存在“cnt”變數中。

• 現在，迭代當前單詞。在對映中將單詞的每個字元的頻率減少“cnt”。

• 在“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)，用於儲存最終字串。