C++에서 재귀 함수가있는 회문 문자열 확인
이 기사에서는 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
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 Facebook