重新排列字串的字符，以形成有效的英文數字表示形式-C++-PHP中文網

重新排列字串的字符，以形成有效的英文數字表示形式

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

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

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

範例範例

輸入 – str = "zeoroenwot"

輸出 – ‘012’

解釋– 我們可以從給定的字串中提取出'zero'、'one'和'two'，然後按照數字的增序進行排序。

輸入 – str = ‘zoertowxisesevn’

輸出 – ‘0267’

Explanation – 我們可以從給定的字串中擷取「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'個獨特的。
我們在『六』中有『x』個獨特的。
我們在‘eight’中有‘gg’個獨特的。
我們可以從「three」中提取出包含「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)，用于存储最终的字符串。

以上是重新排列字串的字符，以形成有效的英文數字表示形式的詳細內容。更多資訊請關注PHP中文網其他相關文章！