数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学将字符串的字符重新排序为有效的英文数字表示
在这个问题中，我们需要将给定字符串的字符重新排序为有效的英文数字表示。第一种方法可以是查找字符串的所有排列，提取与数字相关的英文单词，并将它们转换为数字。
另一种可以用来解决这个问题的方法是，从每个单词中找到一个唯一的字符。在本教程中，我们将学习解决给定问题的两种方法。
问题陈述- 我们得到一个包含小写字符且长度等于N的字符串。该字符串包含[0-9]数字的英文单词表示，顺序随机。我们需要从字符串中提取英文单词，将其转换为数字，并按升序显示这些数字。
示例
输入– str = "zeoroenwot"
输出– ‘012’
解释– 我们可以从给定的字符串中提取“zero”、“one”和“two”，然后我们可以按升序排列数字。
输入– str = ‘zoertowxisesevn’
输出– ‘0267’
解释– 我们可以从给定的字符串中提取“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”是唯一的。
“six”中“x”是唯一的。
“eight”中“g”是唯一的。
我们可以从“three”中取“h”作为唯一字符，因为我们上面已经考虑了所有包含“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)，用于存储最终字符串。
56 次浏览
