在 C++ 中用遞迴函式檢查迴文字串
Jinku Hu
2023年10月12日
本文將介紹幾種在 C++ 中使用遞迴函式檢查迴文字串的方法。
使用遞迴函式檢查迴文字串
遞迴函式是從函式主體中呼叫自身的函式。遞迴方法不是實現迴文校驗演算法的最佳方法。isPalindrome 函式接受三個引數，並返回一個布林值，以指示所傳遞的 string 是否是迴文。第二個和第三個引數用於儲存字串序列的開始和結束位置。作為第一個條件，我們評估字串長度是否為 1，如果是，則函式立即返回一個肯定值。接下來，比較第一個和最後一個字元，如果不相等，則該函式返回 false。否則，執行將繼續檢查字串是否在當前 st 和 en 位置的中間包含更多字元。如果條件評估為真，則使用移位的位置和相同的字串值進行遞迴呼叫。另一方面，錯誤條件會強制函式返回 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 過載版本採用三個引數，其中前兩個指定第一個範圍，而第三個參數列示第二個範圍的開始。
#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
作者： Jinku Hu
