文字列の文字を並べ替えて有効な英語の数値表現を形成します

この問題では、有効な英語の数値表現を取得するために、指定された文字列の文字を並べ替える必要があります。最初のアプローチは、文字列のすべての順列を見つけて、数字に関連する英単語を抽出し、それらを数字に変換することです。

この問題を解決するもう 1 つの方法は、各単語から一意の文字を見つけることです。このチュートリアルでは、特定の問題を解決する 2 つの方法を学びます。

問題ステートメント- 小文字を含む長さ N の文字列が与えられています。この文字列には、数字 [0 ～ 9] の英単語表現がランダムな順序で含まれています。文字列から英単語を抽出し、数値に変換し、その数値を昇順で表示する必要があります。

例例

入力 – str = "ゼオロエンウォット"

出力 –'012'

説明– 指定された文字列から「0」、「1」、「2」を抽出し、それらを昇順に並べ替えることができます。

入力 – str = 'zoertowxisesevn'

出力 –'0267'

説明 – 指定された文字列から「zero」、「two」、「six」、「seven」を抽出できます。

方法 1

このメソッドでは、 next_permutation() メソッドを使用して文字列の順列を取得します。次に、各順列から数字に関連する英単語を抽出し、順列から抽出された単語の最大合計数を追跡します。これから文字列を形成していきます。

＃＃＃アルゴリズム＃＃＃

文字列と単語をパラメータとして受け取る countOccurrences() 関数を定義します。これは、特定の文字列内の特定の単語の出現数をカウントするために使用されます。

変数「count」を定義し、ゼロに初期化します。

• while ループを使用して文字列を走査します。現在の位置で単語が見つかった場合、'count' の値は 1 増加し、'pos' の値は単語の長さだけスキップされます。

• 「count」の値を返します

convertToDigits() 関数は単語を数値に変換するために使用されます

• 数字の英語表現を含む 'words' という名前のベクトルを定義します。また、文字列の任意の順列における最大単語数を格納するために「max_digits」を定義します。さらに、任意の順列から最大の単語を抽出できる場合の各桁の頻度を格納する「digital_freq」マップを定義します。

• sort() メソッドを使用して、指定された文字列を並べ替えます。

• do-while() ループで next_permutations() メソッドを使用します。ループ内で、別のループを使用して単語ベクトルを反復処理します。

• 現在の順列内の各単語の出現数をカウントし、これに基づいて 'word_freq' マップを更新します。同時に、結果の値を「cnt」変数に追加します。

• 「cnt」の値が「max_digitals」より大きい場合は、「max_digitals」と「digital_frequency」の値を更新します。

• 「digit_freq」マップを調べて、数値を文字列に変換します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

  時間計算量 - O(N*N!)。すべての順列を見つける必要があるためです。

空間複雑度 - 最終文字列の保存に O(N)。

方法 2

このメソッドは、上記のメソッドの最適化バージョンです。ここでは、各単語から一意の文字を取得し、この文字に基づいて指定された文字列から正確な単語を検索します。

＃＃＃観察する＃＃＃

「ゼロ」には「z」個の一意のものがあります。

「2」に「w」個の一意の要素があります。

• 「4」個の中に「u」個の固有のものがあります。

• 「6 個」のうち「x」個の固有のものがあります。

• 「eight」には「gg」のユニークなものがあります。

• 上で検討したのと同じように、「three」から「h」を含むすべての一意の単語を抽出できます。

• 「o」を含むすべての単語を考慮したため、「one」から「o」だけを取り出すことができます。

• 上記のように、「f」を含むすべての単語として「five」から「f」を選択できます。

• 「7」には「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 中国語 Web サイトの他の関連記事を参照してください。