Rearrange the characters of a string to form a valid English numeric representation

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

Example Example

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.

method one

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.

algorithm

• 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.

Example

#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);
}

Output

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.

Method Two

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.

observe

• 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.

algorithm

• 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!