在 C++ 中用遞迴函式檢查迴文字串
本文將介紹幾種在 C++ 中使用遞迴函式檢查迴文字串的方法。
使用遞迴函式檢查迴文字串
遞迴函式是從函式主體中呼叫自身的函式。遞迴方法不是實現迴文校驗演算法的最佳方法。isPalindrome 函式接受三個引數，並返回一個布林值，以指示所傳遞的 string 是否是迴文。第二個和第三個引數用於儲存字串序列的開始和結束位置。作為第一個條件，我們評估字串長度是否為 1，如果是，則函式立即返回一個肯定值。接下來，比較第一個和最後一個字元，如果不相等，則該函式返回 false。否則，執行將繼續檢查字串是否在當前 st 和 en 位置的中間包含更多字元。如果條件評估為真，則使用移位的位置和相同的字串值進行遞迴呼叫。另一方面，錯誤條件會強制函式返回 true。
#include <iostream>
#include <string>
using std::cout; using std::endl;
using std::string; using std::cin;
using std::equal; using std::remove;
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::cout; using std::endl;
using std::string; using std::cin;
using std::equal; using std::remove;
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::cout; using std::endl;
using std::string; using std::cin;
using std::equal; using std::remove;
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
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn