In this problem, we need to rearrange the characters of the given string to get a valid English numeric representation. The first approach could be to find all permutations of the string, extract English words related to numbers, and convert them into numbers.
Another way to solve this problem is to find a unique character from each word. In this tutorial, we will learn two ways to solve a given problem.
Problem Statement- We are given a string of length N containing lowercase characters. The string contains English word representations of numbers [0-9] in random order. We need to extract English words from string, convert them to numbers and display these numbers in ascending order
Input – str = "zeoroenwot"
Output –‘012’
Explanation– We can extract 'zero', 'one' and 'two' from the given string and then sort them in increasing numerical order.
Input – str = ‘zoertowxisesevn’
Output –‘0267’
Explanation – We can extract "zero", "two", "six" and "seven" from the given string.
In this method, we will use the next_permutation() method to get the permutation of the string. We will then extract number-related English words from each permutation and keep track of the maximum total number of words extracted from any permutation. From this we will form the string.
Define the countOccurrences() function, which accepts strings and words as parameters. It is used to count the number of occurrences of a specific word in a given string.
Define the variable 'count' and initialize it to zero.
Use a while loop to traverse the string. If we find the word at the current position, the value of 'count' is increased by 1 and the value of 'pos' is skipped by the length of the word.
Return the value of ‘count’
convertToDigits() function is used to convert words into numbers
Define a vector named 'words', which contains the English representation of the number. Also, define ‘max_digits’ to store the maximum number of words in any permutation of the string. Furthermore, define the 'digit_freq' map to store the frequency of each digit when we can extract the maximum word from any permutation.
Use the sort() method to sort the given string.
Use next_permutations() method with do-while() loop. Within the loop, use another loop to iterate over the word vectors.
Count the number of occurrences of each word in the current permutation and update the 'word_freq' map based on this. At the same time, add the resulting value to the 'cnt' variable.
If the value of 'cnt' is greater than 'max_digits', update the values of 'max_digits' and 'digit_frequancy'.
Traverse the "digit_freq" map and convert numbers to strings.
#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
Time complexity - O(N*N!), because we need to find all permutations.
Space complexity - O(N) for storing the final string.
This method is an optimized version of the above method. Here we will take a unique character from each word and find the exact word from the given string based on this character.
We have 'z' unique ones in 'zero'.
We have 'w' uniques in 'two'.
We have 'u' unique ones in 'four'.
We have 'x' unique ones out of 'six'.
We have 'gg' unique ones in 'eight'.
We can extract all unique words containing "h" from "three", just like we considered above.
We can take out the only "o" from "one" because we have considered all words containing "o".
We can select ‘f’ from ‘five’ as all words containing ‘f’ as above.
We have 'v' unique ones in 'seven'.
We can take the ‘i’ from ‘nine’ as all the words containing ‘i’ that we considered above.
Define the 'words' vector containing English words and make sure to follow the example order below as we have considered unique words accordingly. Also, define a vector of unique characters and their numeric representation
Count the frequency of each character and store it in the map.
Traverse the array of unique characters
If the map contains a currently unique character, store its frequency value in the 'cnt' variable.
Now, iterate through the current word. Decrease the frequency of each character of a word by 'cnt' in the map.
在‘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)，用于存储最终的字符串。
The above is the detailed content of Rearrange the characters of a string to form a valid English numeric representation. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
