C++ で文字列内の最初の繰り返し文字を見つける
- C++ で文字列内の最初の繰り返し文字を見つける
- ハッシュ手法を使用して、C++ で文字列内の最初の繰り返し文字を見つける
- ブルートフォース法を使用して、C++ で文字列内の最初の繰り返し文字を見つける
このチュートリアルでは、C++ で文字列内の最初の繰り返し文字を見つける方法を学習します。 この目的を達成するための 3つのアプローチを学習します: ハッシュ手法、ブルート フォース法、およびアルゴリズムの作成です。
C++ で文字列内の最初の繰り返し文字を見つける
アルゴリズムの作成を試みる方法は 2つあります。 1つ目は文字列を左から右にトラバースする方法で、2つ目は文字列を右から左にトラバースし、アクセスした文字を追跡する方法です。 2 番目のアプローチは、実行する比較が少なくて効率的であるため、他のアプローチよりもパフォーマンスが優れています。
ソート アルゴリズムは、O(n Log n) 時間で文字列内の最初の繰り返し文字を見つけるのに役立ちます。 ただし、文字列をループして ASCII コードを使用して文字をハッシュし、ハッシュ配列でループを実行して、繰り返される文字の最小位置を見つけることができます。
コード例:
#include <iostream>
using namespace std;
#define numberChar 256
// left most string
int farLeftStr(string& primeStr) {
// represents the first index
int IndexNum[numberChar];
for (int i = 0; i < numberChar; i++) IndexNum[i] = -1;
// represents the resultIndexNum
int resultStr = INT_MAX;
for (int i = 0; i < primeStr.length(); i++) {
if (IndexNum[primeStr[i]] == -1)
IndexNum[primeStr[i]] = i;
else
resultStr = min(resultStr, IndexNum[primeStr[i]]);
}
return (resultStr == INT_MAX) ? -1 : resultStr;
}
int main() {
string primeStr = "HouseOfTheDragons";
int left = farLeftStr(primeStr);
if (left == -1)
cout << "All characters are distinct or string is empty ";
else
cout << "The first repeating character is: " << primeStr[left];
return 0;
}
出力：
The first repeating character is: o
文字列を左から右にトラバースすることは、すべての文字の最初のインデックスを -1 として初期化することに関して可能です。 繰り返される文字の最初または左端のインデックス (遭遇した場合) を現在の結果と比較できます。
さらに、O(N²) の複雑さを使用して、各文字を調査し、文字列の残りの部分で同じ文字を検索することにより、この問題を解決できます。
ハッシュ手法を使用して、C++ で文字列内の最初の繰り返し文字を見つける
Count 配列は、最初の繰り返し文字を見つけ、文字列内で繰り返される文字の数を保持できます。
ハッシュ手法は、4つの主要なステップで構成されます。
- ハッシュ テーブルを 1つ作成します。
- 文字のスキャン。
- 存在しない場合は、ハッシュ テーブルに文字を挿入します。
- それ以外の場合は、その文字を複製として返します。
コード例:
#include <iostream>
// hashing function object type
#include <unordered_set>
using namespace std;
char getRepeatingChar(string &str) {
unordered_set<char> hashObj;
for (int i = 0; i < str.length(); i++) {
char repChar = str[i];
if (hashObj.find(repChar) != hashObj.end())
return repChar;
else
hashObj.insert(repChar);
}
return '\0';
}
int main() {
string expStr = "GameOfThrones";
cout << "The first repeating character is: " << getRepeatingChar(expStr);
}
出力：
The first repeating character is: e
この問題のもう 1つの有名なバリエーションは、Count が 1 に等しい場合に結果を出力することにより、文字列内の最初の一意の文字または非反復文字を出力することです。 元の手法の拡張バリエーションとして、文字列内のすべての繰り返し文字を出力することは可能ですが、基本的なハッシュ方法ほど単純ではありません。
ユーザーが Count 配列を作成する必要があるため、このメソッドの時間計算量は O(n) になります。 最悪の場合、繰り返しや余分なスペースがない場合、その時間計算量は O(1) になります。
ブルートフォース法を使用して、C++ で文字列内の最初の繰り返し文字を見つける
これは、プログラマーが文字列の各文字をチェックして繰り返し文字を見つけ、対応する結果を出力できるようにする簡単な方法です。 最後の文字列に到達するか、最後の文字がスキャンされると、繰り返し文字は検出されず、既定では繰り返し文字はありません。
最悪のシナリオでは、反復がない場合、その時間計算量は O(n2) であり、最良のシナリオでは O(1) であり、これは 2 番目の位置に繰り返し文字が存在することを表します。 . 一定量のメモリを使用するカウント配列が必要なため、総当たりの方法よりも多く、必要な余分なスペースの合計は O(1)、つまり一定です。
コード例:
#include <iostream>
using namespace std;
int main() {
string expStr = "Hello World!";
string primeExp = "";
// check the boundary of the `expStr` string
if (expStr == primeExp) {
cout << "The string is empty!";
}
for (int a = 0; expStr[a] != '\0'; a++) {
for (int b = a + 1; expStr[b] != '\0'; b++) {
if (expStr[a] == expStr[b]) {
cout << "The first repeating character is: " << expStr[a];
}
break;
}
}
}
出力：
The first repeating character is: l
Hassan is a Software Engineer with a well-developed set of programming skills. He uses his knowledge and writing capabilities to produce interesting-to-read technical articles.
GitHub