C++ で再帰関数を使用して回文文字列をチェックする
この記事では、C++ で再帰関数を使用して回文文字列をチェックするいくつかの方法について説明します。
再帰関数を使用して回文文字列をチェックする
再帰関数は、関数本体から自分自身を呼び出す関数です。再帰的方法は、回文チェックアルゴリズムを実装するための最適な方法ではありません。isPalindrome 関数は 3つの引数を取り、渡された string が回文であるかどうかを示すブール値を返します。2 番目と 3 番目の引数は、文字列シーケンスの開始位置と終了位置を格納するために使用されます。最初の条件として、文字列の長さが 1 であるかどうかを評価し、そうである場合、関数はすぐに肯定値を返します。次に、最初と最後の文字が比較され、等しくない場合、関数は false を返します。それ以外の場合、実行は、文字列に現在の st と en の位置の中央にさらに文字が含まれているかどうかを引き続きチェックします。条件が true と評価された場合、再帰呼び出しは、シフトされた位置と同じ文字列値を使用して行われます。一方、false 条件は、関数に true を返すように強制します。
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::equal;
using std::remove;
using std::string;
bool isPalindrome(const string &s, size_t st, size_t en) {
if (s.length() == 1) return true;
if (s[st] != s[en - 1]) return false;
if (st < en + 1) return isPalindrome(s, st + 1, en - 1);
return true;
}
int main() {
string s1 = "radar";
string s2 = "Was it a cat I saw";
isPalindrome(s1, 0, s1.length()) ? cout << "s1 is a palindrome" << endl
: cout << "s1 is not a palindrome" << endl;
isPalindrome(s2, 0, s2.length()) ? cout << "s2 is a palindrome" << endl
: cout << "s2 is not a palindrome" << endl;
return EXIT_SUCCESS;
}
出力：
s1 is a palindrome
s2 is not a palindrome
前のソリューションでは、s2 オブジェクトなどの大文字と小文字が混在するパリンドロームを識別できないことに注意してください。したがって、すべての有効な回文を正しく求めるには、文字列を同じ大文字に変換し、スペースを削除する必要があります。std::trasform アルゴリズムと erase-remove イディオムを使用して、文字列を isPalindrome 関数と互換性のある形式に解析します。
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::equal;
using std::remove;
using std::string;
bool isPalindrome(const string &s, size_t st, size_t en) {
if (s.length() == 1) return true;
if (s[st] != s[en - 1]) return false;
if (st < en + 1) return isPalindrome(s, st + 1, en - 1);
return true;
}
int main() {
string s2 = "Was it a cat I saw";
transform(s2.begin(), s2.end(), s2.begin(),
[](unsigned char c) { return tolower(c); });
s2.erase(remove(s2.begin(), s2.end(), ' '), s2.end());
isPalindrome(s2, 0, s2.length()) ? cout << "s2 is a palindrome" << endl
: cout << "s2 is not a palindrome" << endl;
return EXIT_SUCCESS;
}
出力：
s2 is a palindrome
回文文字列の std::equal アルゴリズムチェックを使用する
std::equal は C++ 標準テンプレートライブラリの一部であり、範囲を比較するために利用できます。したがって、string クラスにはイテレータインターフェイスがあるため、begin 関数と rbegin 関数を使用してその範囲を指定できます。ただし、次の std::equal オーバーロードバージョンは 3つの引数を取り、最初の 2つは最初の範囲を指定し、3 番目の引数は 2 番目の範囲の開始を示します。
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::equal;
using std::remove;
using std::string;
bool checkPalindrome(string& s) {
string tmp = s;
transform(tmp.begin(), tmp.end(), tmp.begin(),
[](unsigned char c) { return tolower(c); });
tmp.erase(remove(tmp.begin(), tmp.end(), ' '), tmp.end());
if (equal(tmp.begin(), tmp.begin() + tmp.size() / 2, tmp.rbegin())) {
return true;
} else {
return false;
}
}
int main() {
string s1 = "radar";
string s2 = "Was it a cat I saw";
checkPalindrome(s2) ? cout << "s2 is a palindrome" << endl
: cout << "s2 is not a palindrome" << endl;
return EXIT_SUCCESS;
}
出力：
s2 is a palindrome
