在這個(gè)問題中，我們需要重新排列給定字符串的字符，以獲得有效的英文數(shù)字表示。第一種方法可以是找到字符串的所有排列，提取與數(shù)字相關(guān)的英文單詞，并將它們轉(zhuǎn)換為數(shù)字。
另一種解決該問題的方法是從每個(gè)單詞中找到一個(gè)唯一的字符。在本教程中，我們將學(xué)習(xí)解決給定問題的兩種方法。
問題陳述– 我們給出了一個(gè)包含小寫字符且長度為N的字符串。該字符串以隨機(jī)順序包含了[0-9]數(shù)字的英文單詞表示。我們需要從字符串中提取英文單詞，將它們轉(zhuǎn)換為數(shù)字，并按升序顯示這些數(shù)字
示例例子
輸入?– str = “zeoroenwot”
輸出?– ‘012’
解釋– 我們可以從給定的字符串中提取出’zero’、’one’和’two’，然后按照數(shù)字的增序進(jìn)行排序。
輸入?– str = ‘zoertowxisesevn’
輸出?– ‘0267’
Explanation?– 我們可以從給定的字符串中提取出“zero”、“two”、“six”和“seven”。
方法一
在這種方法中，我們將使用next_permutation()方法來獲取字符串的排列。然后，我們將從每個(gè)排列中提取與數(shù)字相關(guān)的英文單詞，并跟蹤從任何排列中提取的最大單詞總數(shù)。根據(jù)這一點(diǎn)，我們將形成字符串。
算法
定義countOccurrences()函數(shù)，它接受字符串和單詞作為參數(shù)。它用于計(jì)算給定字符串中特定單詞的出現(xiàn)次數(shù)。
定義變量‘count’，并將其初始化為零。
使用while循環(huán)遍歷字符串。如果我們在當(dāng)前位置找到了該單詞，則將’count’的值增加1，并將’pos’的值跳過單詞的長度。
返回‘count’的值
convertToDigits() 函數(shù)用于將單詞轉(zhuǎn)換為數(shù)字
定義名為‘words’的向量，其中包含數(shù)字的英文表示。同時(shí)，定義‘max_digits’來存儲字符串的任意排列中的最大單詞數(shù)。此外，定義‘digit_freq’映射來存儲當(dāng)我們可以從任意排列中提取最大單詞時(shí)，每個(gè)數(shù)字的頻率。
使用sort()方法對給定的字符串進(jìn)行排序。
使用 next_permutations() 方法與 do-while() 循環(huán)。在循環(huán)中，使用另一個(gè)循環(huán)來迭代單詞向量。
計(jì)算當(dāng)前排列中每個(gè)單詞的出現(xiàn)次數(shù)，并根據(jù)此更新’word_freq’映射。同時(shí)，將結(jié)果值添加到’cnt’變量中。
如果‘cnt’的值大于‘max_digits’，則更新‘max_digits’和‘digit_frequancy’的值。
遍歷“digit_freq”映射并將數(shù)字轉(zhuǎn)換為字符串。
示例
#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);
}
登錄后復(fù)制
輸出
The string after converting to digits and sorting them in non-decreasing order is 012
登錄后復(fù)制
時(shí)間復(fù)雜度 – O(N*N!)，因?yàn)槲覀冃枰业剿械呐帕小?/p>
空間復(fù)雜度 – O(N)，用于存儲最終的字符串。
方法二
這種方法是上述方法的優(yōu)化版本。在這里，我們將從每個(gè)單詞中取一個(gè)唯一的字符，并根據(jù)這個(gè)字符從給定的字符串中找到確切的單詞。
觀察
我們在‘zero’中有‘z’個(gè)獨(dú)特的。
我們在‘two’中有‘w’個(gè)唯一的。
我們在’four’中有’u’個(gè)獨(dú)特的。
我們在‘六’中有‘x’個(gè)獨(dú)特的。
我們在‘eight’中有‘gg’個(gè)獨(dú)特的。
我們可以從“three”中提取出包含“h”的所有唯一單詞，就像我們上面考慮的那樣。
我們可以從“one”中取出唯一的“o”，因?yàn)槲覀円呀?jīng)考慮了所有包含“o”的單詞。
我們可以從“five”中選擇‘f’作為所有包含‘f’的單詞，如上所述。
我們在“seven”中有‘v’個(gè)獨(dú)特的。
我們可以從“nine”中取出‘i’作為我們上面考慮過的所有包含‘i’的單詞。
算法
定義包含英語單詞的’words’向量，并確保按照下面的示例順序進(jìn)行，因?yàn)槲覀円呀?jīng)相應(yīng)地考慮了唯一的單詞。同時(shí)，定義一個(gè)唯一字符的向量及其數(shù)字表示
統(tǒng)計(jì)每個(gè)字符的頻率并將其存儲在映射中。
遍歷唯一字符的數(shù)組
如果地圖中包含當(dāng)前唯一的字符，則將其頻率值存儲在’cnt’變量中。
現(xiàn)在，遍歷當(dāng)前單詞。在地圖中將單詞的每個(gè)字符的頻率減少’cnt’。
在‘digits’向量中添加一個(gè)單詞，重復(fù)‘cnt’次。
對數(shù)字字符串進(jìn)行排序，并從函數(shù)中返回。
示例
#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);
}
登錄后復(fù)制
輸出
The string after converting to digits and sorting them in non-decreasing order is 0267
登錄后復(fù)制
時(shí)間復(fù)雜度 – O(N)，其中N是字符串的長度。
空間復(fù)雜度 – O(N)，用于存儲最終的字符串。
以上就是重新排列字符串的字符，以形成有效的英文數(shù)字表示形式的詳細(xì)內(nèi)容，更多請關(guān)注www.xfxf.net其它相關(guān)文章！
