C++ 重新排列字符串的字符以得到有效的英文表示

在这个问题中，我们需要重新排列给定字符串的字符，以得到有效的英文表示的数字。第一种方法是找到字符串的所有排列，提取与数字相关的英文单词，并将它们转换为数字。

解决这个问题的另一种方法是从每个单词中找到一个唯一的字符。在本教程中，我们将学习解决给定问题的两种方法。

问题陈述 - 我们给出了一个包含小写字符且长度为N的字符串。该字符串以随机顺序包含[0-9]数字的英文表示。我们需要从字符串中提取英文单词，将它们转换为数字，并以升序显示这些数字。

示例

输入 – str = “zeoroenwot”

输出 – ‘012’

解释 – 我们可以从给定字符串中提取’zero’、’one’和’two’，然后按照升序对数字进行排序。

输入 – str = ‘zoertowxisesevn’

输出 – ‘0267’

解释 – 我们可以从给定字符串中提取’zero’、’two’、’six’和’seven’。

方法1

在这种方法中，我们将使用next_permutation()方法获得字符串的排列。然后，我们将从每个排列中提取与数字相关的英文单词，并跟踪从任何排列中提取的最多单词的总数。根据这个，我们将形成字符串。

步骤

• 定义countOccurrences()函数，它以字符串和单词作为参数。它用于计算给定字符串中特定单词的出现次数。
  • 定义’count’变量，并将其初始化为0。

  • 使用while循环遍历字符串。如果我们在当前位置找到了该单词，将’count’的值增加1，并将’pos’值按单词长度跳过。

  • 返回’count’的值。

• convertToDigits()函数用于将单词转换为数字

• 定义一个名为“ words”的向量，其中包含数字的英文表示。另外，定义’max_digits’来存储任意排列的字符串中的最大单词数。此外，定义’digit_freq’映射，以便在任意排列中提取最大单词数时存储每个数字的频率。

• 使用sort()方法对给定字符串进行排序。

• 使用do-while()循环和next_permutations()方法。在循环中，使用另一个循环迭代单词向量。

• 计算当前排列中每个单词的出现次数，并根据此更新’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)，用于存储最终的字符串。

方法2

这个方法是上面方法的优化版本。在这里，我们会从每个单词中选取一个唯一的字符，并根据这个字符从给定的字符串中找到对应的单词。

观察

• 在“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’，并确保按照下面的示例顺序定义，因为我们根据唯一的单词进行了考虑。另外定义一个存储唯一字符及其数字表示的向量。

• 计算每个字符的频率，并将其存储在map中。

• 遍历唯一字符的数组。

• 如果map中包含当前的唯一字符，则将其频率值存储在‘cnt’变量中。

• 现在，遍历当前单词。在map中将每个字符的频率减去‘cnt’。

• 将一个单词按照‘cnt’的次数添加到‘digits’向量中。

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

示例

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