Substrings and Palindromes
Problem
Problem-Solving
Note that if we assume we've generated all substrings for the input without its first letter, then all we need to add are substrings that include the first letter
Note that if a palindrome is a word where the first and last letters are the same and the rest is also a palindrome
Consider what is the base case for each problem?
Solution
#include <iostream>
#include <string>
using namespace std;
/*
Recursive function to find palindrome
@input string to test if it's a palindrome
@return true if string is a palindrome, false otherwise
*/
bool is_palindrome(string str)
{
// base case
if (str.length() <= 1)
{
return true;
}
// if first and last letter are the same
if (str.substr(0, 1) != str.substr(str.length() - 1))
{
return false;
}
else{
// and the rest of me is a palindrome
return is_palindrome(str.substr(1, str.length() - 2));
}
}
/*
Recursive function to generate all substrings
Bottom line: to generate all substrings,
* generate substrings that include the first letter
* then generate all substrings for the input string WITHOUT the first letter
@param input word to generate substrings for
*/
void print_all_substrings(string input)
{
// base case
if (input.length() == 0)
{
return;
}
// If I generate substrings of the input string that include the input string's first letter
cout << input << endl;
for (int i = input.length() - 1; i > 0; i--)
{
cout << input.substr(0, i) << endl;
}
// And then generate all substrings for the input string WITHOUT its first letter
string input_wo_first_letter = input.substr(1, input.length() - 1);
print_all_substrings(input_wo_first_letter);
// Then I printed all susbtrings of input
}
int main()
{
cout << "Word: ";
string input;
cin >> input;
print_all_substrings(input);
cout << endl;
if (is_palindrome(input))
{
cout << "IT'S A PALINDROME!!!" << endl;
}
else
{
cout << "not a palindrome" << endl;
}
system("pause");
return 0;
}
Back to top