유효한 영어 숫자 표현을 형성하기 위해 문자열 문자를 다시 정렬합니다.

이 문제에서는 유효한 영어 숫자 표현을 얻으려면 주어진 문자열의 문자를 재배열해야 합니다. 첫 번째 접근 방식은 문자열의 모든 순열을 찾아 숫자와 관련된 영어 단어를 추출하여 숫자로 변환하는 것일 수 있습니다.

이 문제를 해결하는 또 다른 방법은 각 단어에서 고유한 문자를 찾는 것입니다. 이 튜토리얼에서는 주어진 문제를 해결하는 두 가지 방법을 배웁니다.

문제 설명- 소문자가 포함된 길이 N의 문자열이 제공됩니다. 문자열에는 숫자 [0-9]의 영어 단어 표현이 무작위 순서로 포함되어 있습니다. 문자열에서 영어 단어를 추출하여 숫자로 변환하고 이 숫자를 오름차순으로 표시해야 합니다

예제 예

입력 – str = "zeoroenwot"

출력 –'012'

설명 – 주어진 문자열에서 '0', '1', '2'를 추출한 다음 숫자가 증가하는 순서로 정렬할 수 있습니다.

입력 – str = 'zoertowxisesevn'

출력 –'0267'

설명 – 주어진 문자열에서 "0", "2", "6" 및 "7"을 추출할 수 있습니다.

방법 1

이 메서드에서는 next_permutation() 메서드를 사용하여 문자열의 순열을 가져옵니다. 그런 다음 각 순열에서 숫자 관련 영어 단어를 추출하고 모든 순열에서 추출된 최대 총 단어 수를 추적합니다. 이것으로부터 우리는 문자열을 형성할 것입니다.

알고리즘

• 문자열과 단어를 매개변수로 받아들이는 countOccurrences() 함수를 정의하세요. 주어진 문자열에서 특정 단어의 발생 횟수를 계산하는 데 사용됩니다.

• 변수 'count'를 정의하고 0으로 초기화하세요.

• 문자열을 탐색하려면 while 루프를 사용하세요. 현재 위치에서 단어를 찾으면 'count' 값은 1만큼 증가하고 'pos' 값은 단어 길이만큼 건너뜁니다.

• 'count' 값을 반환합니다

• convertToDigits() 함수는 단어를 숫자로 변환하는 데 사용됩니다

• 숫자의 영어 표현이 포함된 'words'라는 벡터를 정의합니다. 또한 문자열 순열의 최대 단어 수를 저장하려면 'max_digits'를 정의하십시오. 또한 순열에서 최대 단어를 추출할 수 있을 때 각 숫자의 빈도를 저장하도록 'digit_freq' 맵을 정의합니다.

• sort() 메소드를 사용하여 주어진 문자열을 정렬하세요.

• do-while() 루프와 함께 next_permutations() 메서드를 사용하세요. 루프 내에서 다른 루프를 사용하여 단어 벡터를 반복합니다.

• 현재 순열에서 각 단어의 발생 횟수를 계산하고 이를 기반으로 'word_freq' 맵을 업데이트합니다. 동시에 결과 값을 'cnt' 변수에 추가합니다.

• 'cnt' 값이 'max_digits'보다 큰 경우 'max_digits' 및 'digit_frequancy' 값을 업데이트하세요.

• "digit_freq" 맵을 반복하고 숫자를 문자열로 변환합니다.

예

으아악

출력

으아악

시간 복잡도 - O(N*N!), 모든 순열을 찾아야 하기 때문입니다.

공간 복잡도 - 최종 문자열을 저장하기 위한 O(N)입니다.

방법 2

이 방법은 위 방법의 최적화된 버전입니다. 여기서는 각 단어에서 고유한 문자를 가져와서 이 문자를 기반으로 주어진 문자열에서 정확한 단어를 찾습니다.

관찰

• 'zero'에는 고유한 'z'가 있습니다.

• 'two'에는 독특한 'w'가 있습니다.

• '4' 안에 독특한 'u'가 있어요.

• '6'개 중 'x'개의 고유한 항목이 있습니다.

• '에잇'에는 'gg' 독특한 것들이 있어요.

• 위에서 고려한 것처럼 "3"에서 "h"를 포함하는 모든 고유 단어를 추출할 수 있습니다.

• "o"가 포함된 모든 단어를 고려했기 때문에 "one"에서 유일한 "o"를 제외할 수 있습니다.

• 위와 같이 'f'가 포함된 모든 단어를 'five' 중에서 'f'로 선택할 수 있습니다.

• 세븐에는 독특한 'v'가 있어요.

• 'nine'의 'i'는 위에서 살펴본 'i'가 포함된 모든 단어로 간주할 수 있습니다.

알고리즘

• 영어 단어가 포함된 '단어' 벡터를 정의하고 이에 따라 고유한 단어를 고려했으므로 아래 예시 순서를 따르세요. 또한 고유 문자의 벡터와 숫자 표현을 정의하세요

• 각 캐릭터의 빈도를 세어 지도에 저장하세요.

• 다양한 독특한 캐릭터를 반복해보세요

• 지도에 현재 고유한 문자가 포함되어 있는 경우 해당 문자의 빈도 값을 '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)，用于存储最终的字符串。

위 내용은 유효한 영어 숫자 표현을 형성하기 위해 문자열 문자를 다시 정렬합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!