Susun semula aksara rentetan untuk membentuk perwakilan angka Inggeris yang sah

Dalam masalah ini, kita perlu menyusun semula aksara rentetan yang diberikan untuk mendapatkan perwakilan berangka Inggeris yang sah. Pendekatan pertama adalah untuk mencari semua pilihatur rentetan, mengekstrak perkataan Inggeris yang berkaitan dengan nombor, dan menukarnya kepada nombor.

Satu lagi cara untuk menyelesaikan masalah ini ialah mencari watak unik daripada setiap perkataan. Dalam tutorial ini, kita akan mempelajari dua cara untuk menyelesaikan masalah yang diberikan.

Pernyataan Masalah- Kami diberi rentetan panjang N yang mengandungi aksara kecil. Rentetan mengandungi perwakilan perkataan Inggeris bagi nombor [0-9] dalam susunan rawak. Kita perlu mengekstrak perkataan Inggeris daripada rentetan, menukarkannya kepada nombor dan memaparkan nombor ini dalam tertib menaik

Contoh Contoh

Input – str = "zeoroenwot"

Output –‘012’

Penjelasan– Kita boleh mengekstrak 'sifar', 'satu' dan 'dua' daripada rentetan yang diberikan dan kemudian menyusunnya dalam susunan berangka yang semakin meningkat.

Input – str = ‘zoertowxisesevn’

Output –‘0267’

Penjelasan – Kita boleh mengeluarkan "sifar", "dua", "enam" dan "tujuh" daripada rentetan yang diberikan.

Kaedah 1

Dalam kaedah ini, kami akan menggunakan kaedah next_permutation() untuk mendapatkan pilih atur rentetan. Kami kemudiannya akan mengekstrak perkataan Inggeris yang berkaitan dengan nombor daripada setiap pilih atur dan menjejaki jumlah maksimum perkataan yang diekstrak daripada sebarang pilih atur. Daripada ini kita akan membentuk rentetan.

Algoritma

• Tentukan fungsi countOccurrences(), yang menerima rentetan dan perkataan sebagai parameter. Ia digunakan untuk mengira kejadian perkataan tertentu dalam rentetan tertentu.

• Takrifkan 'bilangan' pembolehubah dan mulakannya kepada sifar.

• Gunakan gelung sementara untuk melintasi rentetan. Jika kita dapati perkataan pada kedudukan semasa, nilai 'count' dinaikkan sebanyak 1 dan nilai 'pos' dilangkau oleh kepanjangan perkataan.

• Kembalikan nilai ‘count’

Fungsi

• convertToDigits() digunakan untuk menukar perkataan kepada nombor

• Tentukan vektor bernama 'perkataan', yang mengandungi perwakilan nombor Inggeris. Juga, takrifkan 'max_digits' untuk menyimpan bilangan maksimum perkataan dalam sebarang pilih atur rentetan. Selain itu, takrifkan peta 'digit_freq' untuk menyimpan kekerapan setiap digit apabila kita boleh mengekstrak perkataan maksimum daripada sebarang pilih atur.

• Gunakan kaedah sort() untuk mengisih rentetan yang diberikan.

• Gunakan kaedah next_permutations() dengan gelung do-while(). Dalam gelung, gunakan gelung lain untuk mengulangi perkataan vektor.

• Kira kejadian setiap perkataan dalam pilih atur semasa dan kemas kini peta 'word_freq' berdasarkan ini. Pada masa yang sama, tambahkan nilai yang terhasil pada pembolehubah 'cnt'.

• Jika nilai 'cnt' lebih besar daripada 'max_digit', kemas kini nilai 'max_digit' dan 'digit_frequancy'.

• Gelung melalui peta "digit_freq" dan tukar nombor kepada rentetan.

Contoh

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

Output

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

Kerumitan masa - O(N*N!), kerana kita perlu mencari semua pilih atur.

Kerumitan ruang - O(N) untuk menyimpan rentetan akhir.

Kaedah 2

Kaedah ini adalah versi yang dioptimumkan daripada kaedah di atas. Di sini kita akan mengambil watak unik daripada setiap perkataan dan mencari perkataan yang tepat daripada rentetan yang diberikan berdasarkan watak ini.

Perhatikan

• Kami mempunyai 'z' yang unik dalam 'sifar'.

• Kami mempunyai 'w' yang unik dalam 'dua'.

• Kami mempunyai 'u' yang unik dalam 'empat'.

• Kami mempunyai 'x' unik daripada 'enam'.

• Kami mempunyai 'gg' yang unik dalam 'lapan'.

• Kami boleh mengekstrak semua perkataan unik yang mengandungi "h" daripada "tiga", seperti yang kami pertimbangkan di atas.

• Kita boleh mengeluarkan satu-satunya "o" daripada "satu" kerana kita telah mempertimbangkan semua perkataan yang mengandungi "o".

• Kita boleh memilih 'f' daripada 'lima' kerana semua perkataan mengandungi 'f' seperti di atas.

• Kami mempunyai yang unik 'v' dalam "tujuh".

• Kita boleh mengambil 'i' daripada 'sembilan' kerana semua perkataan yang mengandungi 'i' yang kita pertimbangkan di atas.

Algoritma

• Takrifkan vektor 'perkataan' yang mengandungi perkataan Inggeris dan pastikan anda mengikut susunan contoh di bawah kerana kami telah mempertimbangkan perkataan unik dengan sewajarnya. Juga, tentukan vektor aksara unik dan perwakilan berangkanya

• Kira kekerapan setiap aksara dan simpannya dalam peta.

• Gelung melalui pelbagai watak unik

• Jika peta mengandungi aksara unik pada masa ini, simpan nilai kekerapannya dalam pembolehubah 'cnt'.

• Sekarang, ulangi perkataan semasa. Kurangkan kekerapan setiap aksara perkataan dengan 'cnt' dalam peta.

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

Atas ialah kandungan terperinci Susun semula aksara rentetan untuk membentuk perwakilan angka Inggeris yang sah. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!