在這個問題中，我們需要重新排列給定字串的字符，以獲得有效的英文數字表示。第一種方法可以是找到字串的所有排列，提取與數字相關的英文單詞，並將它們轉換為數字。
另一種解決該問題的方法是從每個單字中找到一個唯一的字元。在本教程中，我們將學習解決給定問題的兩種方法。
問題陳述- 我們給了一個包含小寫字元且長度為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中文網其他相關文章！
