import java.util.*;
class Palindrome
{
public static void main(String args[])
{
String original, reverse = "";
Scanner in = new Scanner(System.in);
System.out.println("Enter a string to check if it is a palindrome");
original = in.nextLine();
int length = original.length();
for ( int i = length - 1; i >= 0; i-- )
reverse = reverse + original.charAt(i);
if (original.equals(reverse)) System.out.println("Entered string is a palindrome.");
else
System.out.println("Entered string is not a palindrome.");
}
}
//Another Method
import java.util.*;
class Palindrome
{
public static void main(String args[])
{
String inputString;
Scanner in = new Scanner(System.in);
System.out.println("Input a string");
inputString = in.nextLine();
int length = inputString.length();
int i, begin, end, middle;
begin = 0;
end = length - 1;
middle = (begin + end)/2;
for (i = begin; i <= middle; i++)
{
if (inputString.charAt(begin) == inputString.charAt(end))
{
begin++;
end--;
}
else
{
break;
}
}
if (i == middle + 1)
{
System.out.println("Palindrome");
}
else
{
System.out.println("Not a palindrome");
}
}
}
First Method: Using Reverse String Comparison
Let’s break down the first approach where the string is reversed and compared with the original string.
1. Class Definition:
class Palindrome
The class Palindrome is declared. Here, the main method will be defined. It is the point of entry for the program.
2. Main Method:
public static void main(String args[])
Declaring the main method point of execution.
3. Variable Declarations:
String original, reverse = “”;
Scanner in = new Scanner(System.in);
- Original: This variable will hold the original input string.
- reverse: This variable will hold the reversed string. It is initialized as an empty string.
- Scanner in = new Scanner(System.in): A Scanner object is created to read user input from the console.
4. Prompting User for Input:
System.out.println(“Enter a string to check if it is a palindrome”);
original = in.nextLine();
The program prompts the user to enter a string, and the input string is assigned to the variable original.
5. Reverse the String:
int length = original.length();
for (int i = length – 1; i >= 0; i–)
reverse = reverse + original.charAt(i);
- length holds the length of the input string.
- A for loop starts from the last character of the string (i = length – 1) and moves backward (i–), extracting each character using original.charAt(i) and appending it to the reverse string. This reverses the string.
6. Checking Palindrome:
if (original.equals(reverse))
System.out.println(“Entered string is a palindrome.”);
else
System.out.println(“Entered string is not a palindrome.”);
- It checks if the original string equals the reversed one using original.equals(reverse).
- If they are equal, then it prints “Entered string is a palindrome.”. If they do not equal, it prints “Entered string is not a palindrome.”.
Sample Input and Output for the First Method:
Input: “madam”
Output: “Entered string is a palindrome.”
Second Method: Using Two Pointers to Compare Characters
The second approach uses two pointers to compare characters from both ends of the string towards the centre.
1. Class Definition:
class Palindrome
The second class also has almost the same definition as that of the above class but it is also known as Palindrome. It only checks whether any provided string is a palindrome in another way.
2. Main Method:
public static void main(String args[])
Just as the main is used above, here also.
3. Variable Declarations:
String inputString;
Scanner in = new Scanner(System.in);
- inputString: This variable is used to store the string entered by the user.
- Scanner in = new Scanner(System.in): It is used to create a Scanner object that reads input from the user.
4. Inputting User Data
System.out.println(“Input a string”);
inputString = in.nextLine();
This function will prompt the user to enter a string and then it will store the entered value in inputString.
5. Initializing Pointers:
int length = inputString.length();
int i, begin, end, middle;
begin = 0;
end = length – 1;
middle = (begin + end) / 2;
- ‘length’ stores the length of the input string.
- ‘begin’ and ‘end’ are pointers. ‘begin’ starts at index 0 (first character), and ‘end’ starts at the last index of the string (length – 1).
- ‘middle’ is the index that represents the midpoint of the string (this will help to stop the comparison once the pointers meet).
6. Compare Characters Using Two Pointers:
for (i = begin; i <= middle; i++)
{
if (inputString.charAt(begin) == inputString.charAt(end))
{
begin++;
end–;
}
else
{
break;
}
}
- A for loop runs from begin to middle. The loop compares the characters at positions begin and end using inputString.charAt(begin) and inputString.charAt(end).
- If the characters match, then pointers begin and end move toward the center (begin++ and end–).
- If the characters do not match, the loop breaks and the string is not a palindrome.
7. Checking the Result:
if (i == middle + 1)
{
System.out.println(“Palindrome”);
} else
{
System.out.println(“Not a palindrome”);
}
- If the loop runs fine and i becomes equal to middle + 1, then string is a palindrome. And the string “Palindrome” is printed out.
- If the loop terminates because of premature termination due to mismatch, then message “Not a palindrome” will be printed.
Sample Input and Output for the above Method:
Input: “racecar”
Output: “Palindrome”
Both Methods Comparison
1. First Method (Reversal Approach):
- It reverses the entire string and compares the reversed string with the original string.
- Time complexity: (O(n)), where n is the string length because it iterates over every character in a string to reverse a string.
- Space complexity: (O(n)) because the reversed string is returned separately.
2. The second solution using The Pointers Technique
- It compares both ends of the strings and moves one step towards the centre.
- Time complexity: (O(n)), where (n) is the length of the string (we compare each character at most once).
- Space complexity: (O(1)), since it doesn’t require any additional storage for reversed strings.
Both check whether a string is a palindrome. The second method, using pointers, uses less space in memory since it does not require a second space for the reversed string, but the reversal method is much more intuitive and only uses one extra space. Both methods have linear time complexity, (O(n)).