InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
Check if a string is a palindrome or not? |
|
Answer» Palindrome: A string is called a palindrome if it can be read the same way starting from the front (or) starting from the back. In other words, a string is a palindrome if the reverse of the string is equal to the original string. Naive Implementation: #include<iostream>#include<string>#include<algorithm>using namespace std;// To reverse a stringstring reverseString(string str){ int len = str.length(); int mid = len / 2; // Traverse until mid and swap characters from ends for (int i = 0; i < mid; i++) swap(str[i], str[len - i - 1]); return str;}BOOL isPalindrome(string a){ // This reverse the string string b = reverseString(a); // Check if REVERSED string and original string are same return a == b;}int main(){ string s1 = "BANANA"; string s2 = "MADAM"; cout<<s1<<" is "<< (isPalindrome(s1) ? "NOT ": "") <<" a PALINDROME\n"; cout<<s2<<" is "<< (isPalindrome(s2) ? "NOT ": "") <<" a PALINDROME\n";}Output: BANANA is NOT a PALINDROMEMADAM is a PALINDROMEThis approach has a Time Complexity of O(N) and ALSO Space Complexity of O(N). A better version to solve this is to not create the actual copy but use 2 pointers one from start and another from the end to check if these 2 pointers POINT to the same characters and move them until the midpoint of the string. #include<iostream>#include<string>#include<algorithm>using namespace std;bool isPalindrome(string a){ int len = a.length(); int start = 0; int end = len-1; while(start < end) { // if not same then return false if(a[start] != a[end]) { return false; } // update the start and end start++; end--; } // If it had reached upto this, then all characters are equal until mid return true;}int main(){ string s1 = "BANANA"; string s2 = "MADAM"; cout<<s1<<" is "<< (isPalindrome(s1) ? "NOT ": "") <<" a PALINDROME\n"; cout<<s2<<" is "<< (isPalindrome(s2) ? "NOT ": "") <<" a PALINDROME\n";}Output: BANANA is NOT a PALINDROMEMADAM is a PALINDROMEThis approach has a Time Complexity of O(N). Space Complexity is O(1) as we are not making a copy of the string here. |
|