Given a sentence s, the task is to check if it is a palindrome sentence or not. A palindrome sentence is a sequence of characters, such as a word, phrase, or series of symbols, that reads the same backward as forward after converting all uppercase letters to lowercase and removing all non-alphanumeric characters.
Examples:
Input: s = “Too hot to hoot.”
Output: True
Explanation: If we remove all non-alphanumeric characters and convert all uppercase letters to lowercase, string s will become “toohottohoot” which is a palindrome.
Input: s = “Abc 012..## 10cbA”
Output: True
Explanation: If we remove all non-alphanumeric characters and convert all uppercase letters to lowercase, string s will become “abc01210cba” which is a palindrome.
Input: s = “ABC $. def01ASDF..”
Output: False
Explanation: If we remove all non-alphanumeric characters and convert all uppercase letters to lowercase, string s will become “abcdef01asdf” which is not a palindrome.
[Naive Approach] Comparing original and reversed strings – O(n) Time and O(n) Space
A simple approach is to create a new string containing only the alphanumeric characters of the original string. Also, in case of uppercase letters convert them to lowercase. Then, compare this new string with its reverse to know if the sentence is a palindromic sentence or not.
C++
// C++ program to check string for palindrome
// by comparing original and reversed strings
#include <algorithm>
#include <iostream>
using namespace std;
bool sentencePalindrome(string &s) {
// create a new string having only
// alphanumeric characters
string s1 = "";
for (char ch : s) {
if (isalnum(ch)) {
s1.push_back(tolower(ch));
}
}
// find reverse of this new string
string rev = s1;
reverse(rev.begin(), rev.end());
// compare string and its reverse
return s1 == rev;
}
int main() {
string s = "Too hot to hoot.";
cout << (sentencePalindrome(s) ? "True" : "False") << endl;
return 0;
}
// Java program to check string for palindrome by comparing
// original and reversed strings
import java.util.*;
class GfG {
static boolean sentencePalindrome(String s) {
// create a new string having only
// alphanumeric characters
StringBuilder s1 = new StringBuilder();
for (char ch : s.toCharArray()) {
if (Character.isLetterOrDigit(ch)) {
s1.append(Character.toLowerCase(ch));
}
}
// find reverse of this new string
StringBuilder rev = new StringBuilder(s1.toString());
rev.reverse();
// compare string and its reverse
return s1.toString().equals(rev.toString());
}
public static void main(String[] args) {
String s = "Too hot to hoot.";
System.out.println(sentencePalindrome(s)
? "True" : "False");
}
}
# Python program to check string for palindrome
# by comparing original and reversed strings
def sentencePalindrome(s):
# create a new list having only
# alphanumeric characters
s1 = []
for ch in s:
if ch.isalnum():
s1.append(ch.lower())
# Convert the new list to string
s1 = ''.join(s1)
# find reverse of this new string
rev = s1[::-1]
# compare string and its reverse
return s1 == rev
if __name__ == "__main__":
s = "Too hot to hoot."
print("True" if sentencePalindrome(s) else "False")
// C# program to check string for palindrome
// by comparing original and reversed strings
using System;
using System.Text;
using System.Linq;
class GfG {
// Function to check if the sentence is a palindrome
static bool sentencePalindrome(ref string s) {
StringBuilder s1 = new StringBuilder();
// Filter out non-alphanumeric characters and
// convert to lowercase
foreach (char ch in s) {
if (Char.IsLetterOrDigit(ch))
s1.Append(Char.ToLower(ch));
}
string s2 = s1.ToString();
// find reverse of this new string
char[] revArray = s2.ToCharArray().Reverse().ToArray();
string rev = new string(revArray);
// compare string and its reverse
return s2 == rev;
}
static void Main() {
string s = "Too hot to hoot.";
Console.WriteLine(sentencePalindrome(ref s) ? "True" : "False");
}
}
// JavaScript program to check string for palindrome
// by comparing original and reversed strings
function sentencePalindrome(s) {
// create an array to store only alphanumeric characters
let s1 = [];
for (let i = 0; i < s.length; i++) {
let ch = s[i];
// Check if the character is alphanumeric
if (/[a-zA-Z0-9]/.test(ch)) {
s1.push(ch.toLowerCase());
}
}
// find reverse of this new string by joining the array
// into a string
let rev = s1.slice().reverse().join("");
// compare string and its reverse
return s1.join("") === rev;
}
let s = "Too hot to hoot.";
console.log(sentencePalindrome(s) ? "True" : "False");
[Expected Approach] Using Two Pointers – O(n) Time and O(1) Space
The idea is to use two pointers approach to find if a sentence is palindrome or not. Maintain one pointer at the beginning and the other at the end of the sentence. The pointers move towards each other, comparing characters along the way. If the characters match, we continue moving both pointers inward; if they differ, we return false, indicating the sentence is not a palindrome.
Also, while comparing we skip all non-alphanumeric characters. Finally, if the pointers cross each other, this means that the sentence is a palindrome.
C++
// C++ program to find if a sentence is
// palindrome using two pointers
#include <iostream>
using namespace std;
// To check sentence is palindrome or not
bool sentencePalindrome(string s) {
int i = 0, j = s.length() - 1;
// Compares character until they are equal
while (i < j) {
// Skip non alphabet character
// from left side
if (!isalnum(s[i]))
i++;
// Skip non alphabet character
// from right side
else if (!isalnum(s[j]))
j--;
// If characters are equal
// update the pointers
else if (tolower(s[i]) == tolower(s[j]))
i++, j--;
// If characters are not equal then
// sentence is not palindrome
else
return false;
}
// Return true as sentence is palindrome
return true;
}
int main() {
string s = "Too hot to hoot.";
cout << (sentencePalindrome(s) ? "True" : "False") << endl;
return 0;
}
// C program to find if a sentence is
// palindrome using two pointers
#include <stdio.h>
#include <stdbool.h>
// To check sentence is palindrome or not
bool sentencePalindrome(const char* s) {
int i = 0, j = strlen(s) - 1;
// Compares character until they are equal
while (i < j) {
// Skip non alphabet character
// from left side
if (!isalnum(s[i]))
i++;
// Skip non alphabet character
// from right side
else if (!isalnum(s[j]))
j--;
// If characters are equal
// update the pointers
else if (tolower(s[i]) == tolower(s[j]))
i++, j--;
// If characters are not equal then
// sentence is not palindrome
else
return false;
}
// Return true as sentence is palindrome
return true;
}
int main() {
const char* s = "Too hot to hoot.";
printf("%s\n", sentencePalindrome(s) ? "True" : "False");
return 0;
}
// Java program to find if a sentence is
// palindrome using two pointers
class GfG {
// To check sentence is palindrome or not
static boolean sentencePalindrome(String s) {
int i = 0, j = s.length() - 1;
// Compares character until they are equal
while (i < j) {
// Skip non alphabet character from left side
if (!Character.isLetterOrDigit(s.charAt(i)))
i++;
// Skip non alphabet character from right side
else if (!Character.isLetterOrDigit(s.charAt(j)))
j--;
// If characters are equal update the pointers
else if (Character.toLowerCase(s.charAt(i))
== Character.toLowerCase(s.charAt(j))) {
i++;
j--;
}
// If characters are not equal then sentence
// is not palindrome
else
return false;
}
// Return true as sentence is palindrome
return true;
}
public static void main(String[] args) {
String s = "Too hot to hoot.";
System.out.println(sentencePalindrome(s)
? "True" : "False");
}
}
# Python program to find if a sentence is
# palindrome using two pointers
# To check sentence is palindrome or not
def sentencePalindrome(s):
i, j = 0, len(s) - 1
# Compares character until they are equal
while i < j:
# Skip non alphabet character
# from left side
if not s[i].isalnum():
i += 1
# Skip non alphabet character
# from right side
elif not s[j].isalnum():
j -= 1
# If characters are equal
# update the pointers
elif s[i].lower() == s[j].lower():
i += 1
j -= 1
# If characters are not equal then
# sentence is not palindrome
else:
return False
# Return true as sentence is palindrome
return True
if __name__ == "__main__":
s = "Too hot to hoot."
print("True" if sentencePalindrome(s) else "False")
// C# program to find if a sentence is
// palindrome using two pointers
using System;
class GfG {
// To check sentence is palindrome or not
static bool sentencePalindrome(string s) {
int i = 0, j = s.Length - 1;
// Compares character until they are equal
while (i < j) {
// Skip non alphabet character
// from left side
if (!char.IsLetterOrDigit(s[i]))
i++;
// Skip non alphabet character
// from right side
else if (!char.IsLetterOrDigit(s[j]))
j--;
// If characters are equal
// update the pointers
else if (char.ToLower(s[i]) == char.ToLower(s[j])) {
i++;
j--;
}
// If characters are not equal then
// sentence is not palindrome
else
return false;
}
// Return true as sentence is palindrome
return true;
}
static void Main() {
string s = "Too hot to hoot.";
Console.WriteLine(sentencePalindrome(s) ? "True" : "False");
}
}
// JavaScript program to find if a sentence is
// palindrome using two pointers
// To check sentence is palindrome or not
function sentencePalindrome(s) {
let i = 0, j = s.length - 1;
// Compares character until they are equal
while (i < j) {
// Skip non alphabet character
// from left side
if (!s[i].match(/[a-zA-Z0-9]/))
i++;
// Skip non alphabet character
// from right side
else if (!s[j].match(/[a-zA-Z0-9]/))
j--;
// If characters are equal
// update the pointers
else if (s[i].toLowerCase() === s[j].toLowerCase())
i++, j--;
// If characters are not equal then
// sentence is not palindrome
else
return false;
}
// Return true as sentence is palindrome
return true;
}
// Driver Code
let s = "Too hot to hoot.";
console.log(sentencePalindrome(s) ? "True" : "False");