在這個問題中，我們需要重新排列給定字符串的字符，以獲得有效的英文數字表示。第一種方法可以是找到字符串的所有排列，提取與數字相關的英文單詞，并將它們轉換為數字。
另一種解決該問題的方法是從每個單詞中找到一個唯一的字符。在本教程中，我們將學習解決給定問題的兩種方法。
問題陳述– 我們給出了一個包含小寫字符且長度為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)，用于存儲最終的字符串。
以上就是重新排列字符串的字符，以形成有效的英文數字表示形式的詳細內容，更多請關注www.xfxf.net其它相關文章！
