在這個(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)遍歷字符串。如果我們?cè)诋?dāng)前位置找到了該單詞,則將’count’的值增加1,并將’pos’的值跳過單詞的長度。
返回‘count’的值
convertToDigits() 函數(shù)用于將單詞轉(zhuǎn)換為數(shù)字
定義名為‘words’的向量,其中包含數(shù)字的英文表示。同時(shí),定義‘max_digits’來存儲(chǔ)字符串的任意排列中的最大單詞數(shù)。此外,定義‘digit_freq’映射來存儲(chǔ)當(dāng)我們可以從任意排列中提取最大單詞時(shí),每個(gè)數(shù)字的頻率。
使用sort()方法對(duì)給定的字符串進(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),用于存儲(chǔ)最終的字符串。
方法二
這種方法是上述方法的優(yōu)化版本。在這里,我們將從每個(gè)單詞中取一個(gè)唯一的字符,并根據(jù)這個(gè)字符從給定的字符串中找到確切的單詞。
觀察
我們?cè)凇畓ero’中有‘z’個(gè)獨(dú)特的。
我們?cè)凇畉wo’中有‘w’個(gè)唯一的。
我們?cè)?#8217;four’中有’u’個(gè)獨(dú)特的。
我們?cè)凇杏小畑’個(gè)獨(dú)特的。
我們?cè)凇甧ight’中有‘gg’個(gè)獨(dú)特的。
我們可以從“three”中提取出包含“h”的所有唯一單詞,就像我們上面考慮的那樣。
我們可以從“one”中取出唯一的“o”,因?yàn)槲覀円呀?jīng)考慮了所有包含“o”的單詞。
我們可以從“five”中選擇‘f’作為所有包含‘f’的單詞,如上所述。
我們?cè)凇皊even”中有‘v’個(gè)獨(dú)特的。
我們可以從“nine”中取出‘i’作為我們上面考慮過的所有包含‘i’的單詞。
算法
定義包含英語單詞的’words’向量,并確保按照下面的示例順序進(jìn)行,因?yàn)槲覀円呀?jīng)相應(yīng)地考慮了唯一的單詞。同時(shí),定義一個(gè)唯一字符的向量及其數(shù)字表示
統(tǒng)計(jì)每個(gè)字符的頻率并將其存儲(chǔ)在映射中。
遍歷唯一字符的數(shù)組
如果地圖中包含當(dāng)前唯一的字符,則將其頻率值存儲(chǔ)在’cnt’變量中。
現(xiàn)在,遍歷當(dāng)前單詞。在地圖中將單詞的每個(gè)字符的頻率減少’cnt’。
在‘digits’向量中添加一個(gè)單詞,重復(fù)‘cnt’次。
對(duì)數(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),用于存儲(chǔ)最終的字符串。
以上就是重新排列字符串的字符,以形成有效的英文數(shù)字表示形式的詳細(xì)內(nèi)容,更多請(qǐng)關(guān)注www.xfxf.net其它相關(guān)文章!