how to check whether a word is a palindrome

[nitin ratra]

given "NITIN" how do i chek it is a palindrome ... m a begginer.

[edit]Added details to subject. CR[/edit]
[ August 14, 2008: Message edited by: Campbell Ritchie ]

[Sagar Rohankar]

If you googled it , you got hundreds of links to do this program ! But If you are beginner and just started a programming with Java, I suggest you show your efforts first ! Put your logic and the code that you done so far !

We are here to help you !
[ August 11, 2008: Message edited by: Sagar Rohankar ]

[Tom Blough]

Compare the first character with the last character, if they are not the same, it is not a palindrome. If they are the same, compare the second character with the second to the last character. If they are not the same, then it is not a palindrome. If they are the same, repeat the above.

Whenever the characters are not the same, it is not a palindrome and you can stop. If you reach the middle of the string (I'll leave you to figure out how to tell that), then the string is a palindrome.

[nitin ratra]

hi think it must be tested by the for loops but i want only a program to test for "NITIN" and without buffered reader ....




what i did was ...
for(i=1;1<5;1++){
1term= lastterm
2nd term = second last term
}

[nitin ratra]

Compare the first character with the last character, if they are not the same, it is not a palindrome. If they are the same, compare the second character with the second to the last character. If they are not the same, then it is not a palindrome. If they are the same, repeat the above.

Whenever the characters are not the same, it is not a palindrome and you can stop. If you reach the middle of the string

wat is the code for this

[Sagar Rohankar]

 

Originally posted by nitin ratra:
hi think it must be tested by the for loops but i want only a program to test for "NITIN" and without buffered reader ....




what i did was ...
for(i=1;1<5;1++){
1term= lastterm
2nd term = second last term
}

Ok, If you want to check out the code for "nitin" only, no problem , you can modify it for any string later ! but first the problem with your code .

 for(i=1;1<5;1++){
[B]1term= lastterm
2nd term = second last term[/B]
} 

If you know What exactly a "palindrome" means, then you shouldn't be matching the last and second last term !

I just want that ,you should try it yourself , without our brains, because that's What JavaRanch is for, to help you in learning !

[Sagar Rohankar]

 

Originally posted by nitin ratra:
Compare the first character with the last character, if they are not the same, it is not a palindrome. If they are the same, compare the second character with the second to the last character. If they are not the same, then it is not a palindrome. If they are the same, repeat the above.

Whenever the characters are not the same, it is not a palindrome and you can stop. If you reach the middle of the string

wat is the code for this

Ohh sorry nitin, Just a little bit late in reply , Your logic and approach is fine ! You just to put same basic operation in your program !, You can try some loop , match the alphabet and decide whether to continue or exit ,saying "Not Palindrome" !!

Whatever you write, post that here. We try to correct you !

[Rob Spoor]

 

Originally posted by nitin ratra:
wat is the code for this

That's what you have to figure out yourself. We will only help you out. See also ShowSomeEffort, NotACodeMill and DoYourOwnHomeWork.

I'll give you some hints:
- you can get the character at a certain position using charAt(int index). The index is 0 based.
- you can get the total number of characters using length().
- the last index of the string is at position length() - 1.
[ August 11, 2008: Message edited by: Rob Prime ]

[nitin ratra]

for (int i = 0; i < len; i++) {
tempCharArray = palindrome.charAt(i);
}

// reverse array of chars
for (int j = 0; j < len; j++) {
charArray[j] = tempCharArray[len - 1 - j];
}


if i dont want to do vt reversal method ,... i mean
wat i want to do is to :

1) CHEK FIRST AND LAST NUMBER
if they are equal then
2)CHEK SECOND AND SECOND LAST NUMBER
if they are equal then
3) THE MIDDLE NUMBER "T" COMES , I CHEK T WITH T
...
SO THIS IS WAT I AM THINKING OF DOING IN A VERY SIMPLY MANNER ....
CAN U HELP MEE OUT

I KNO I HAVE TO USE FOR LOOP FOR THIS BUT , M CONFUSED HOW TO APLY FOR LOOP
PLZZZZZZZZZZ MAN CAN SUM1 NOW GIVE MEE A FULL CODE OF THIS PROGRAM , MY MIND IS EXHAUSTED
REGARDS
NITIN...

[Campbell Ritchie]

Welcome to JavaRanch

Please don't write ALL UPPER CASE. Please indent your code and Use Code Tags to preserve the indentation. Please don't write SUM1 for someone (similarly U, MEE) for reasons given in this FAQ.

*************************************************************************

Like many beginners, you are putting far more code in than you actually need. I often find when beginners ask me for help, I can say, "Delete that, that and that, because you don't need them."

Tom Blough has told you exactly what you need to do; you can get away with a single line inside your loop. You don't actually need all those arrays. You have already been told we don't simply provide answers; please show us a nice simple and short version of what you have got.
And you don't look for 1st character, 2nd character, etc. What a for-loop does is start with a character, then find the next character, then next, until it is told to stop. There are methods in the String class for everything you need.
[ August 11, 2008: Message edited by: Campbell Ritchie ]

[nitin ratra]

step1. mid_index = (total_length - 1)/2 (for odd) or (total_length/2)-1 for even

step2. max_index = total_length - 1 (to pick up letters from end)

step2. loop_index = 0

step3. pick letter at loop_index, pick letter at max_index - loop_index

step4. compare them, if not equal, print "not palindrome" and exit.

step5. loop_index = loop_index + 1

step6. if loop_index > mid_index goto step7 else goto step3

step7. end of loop, and no mismatch found. Hence print "palindrome" and exit.

[Rob Spoor]

Sounds good to me. Can you now translate this in code yourself? total_length can be retrieved using the length() method, and "pick letter at loop_index, pick letter at max_index - loop_index" can be achieved by charAt(loop_index) and charAt(max_index - loop_index).

[nitin ratra]

I am trying to translate this into code , but 4 the last I am struggling with this problem if I get a little Idea .Then it will be helpfull to translate as I am a beginner .

[Campbell Ritchie]

Simplification:

There is no need to use different formulae for division for odd numbers and even numbers. If you use array.length / 2 it will work in both instances.

[Sagar Rohankar]

 

Originally posted by nitin ratra:
step1. mid_index = (total_length - 1)/2 (for odd) or (total_length/2)-1 for even

step2. max_index = total_length - 1 (to pick up letters from end)

step2. loop_index = 0

step3. pick letter at loop_index, pick letter at max_index - loop_index

step4. compare them, if not equal, print "not palindrome" and exit.

step5. loop_index = loop_index + 1

step6. if loop_index > mid_index goto step7 else goto step3

step7. end of loop, and no mismatch found. Hence print "palindrome" and exit.

If you can write this then you can write the code, write down whatever you understand from above steps ! Post it here , no matter how many error the code may have !!

Use single for loop , and string functions that Rob told you !!

[Rob Spoor]

Also, character comparison can be done using ==

[nitin ratra]

Thanks to all of you people who answered my question.I got great help from you people.

[Campbell Ritchie]

Have you got it working? Let's see it please

[nitin ratra]

str="nitin"
len = str.length();
for(int i =0 ; i < len/2; i++)
{
if(str.charat(i) == str.charat(len -1 + i))
continue;
else
print("not paslin");
}

[Rob Spoor]

You might want to break; out of the loop after print that statement, but for the rest that's excellent code (if you remove the copying typos).

[nitin ratra]

ok

[Larry Frissell]

 

Originally posted by nitin ratra:
if(str.charat(i) == str.charat(len -1 + i))
}

In the line above you should subtract i like this >> str.charAt(len -1 - i)); otherwise you will have an out of range exception.

[Rob Spoor]

You're right, I completely missed that.

[Campbell Ritchie]

I would have done something like this, which avoids break and continue:

String name = "Something or other".toLowerCase().replaceAll(" ", "");
boolean isPalindrome = true;
for (int i = 0; isPalindrome && i < name.length() / 2; i++)
{
isPalindrome = (name.charAt(i) == name.charAt(name.length() - i - 1));
}
System.out.printf("The word %s a palindrome.%n", isPalindrome ? "is" : "is not");

If you have several words, you usually make it case-insensitive and remove spaces.

[K. Tsang]

I would have done it something like given string str is the input:

int midpoint=0;
char[] ary = str.toLowerCase().replaceAll(" ", "").toCharArray();
if(ary.size()%2 == 0) midpoint = ary.size()/2;
else midpoint = Integer.parseInt(ary.size()/2); //+1?
for(int i=0; i < midpoint; i++){
for(int j=ary.size(); j > midpoint; j--){
if(!ary[i].equals(ary[j])) Sytem.out.println("Not Palindrome"); break;
} }
System.out.println("Is Palindrome");

The !ary[i].equals(ary[j]) can be ary[i] != ary[j] for chars.

[Larry Frissell]

My solution was a little different, I avoided the for loop (used a while loop) and checked for single character or null inputs.

boolean done = false;
boolean palindrome = true;
s= "saippuakivikauppias";//Finnish word (soap-stone vendor) the world's longest[Wikipedia]
int index = 0;
while(!done){
// check for single character
if ((s.length()<=2)){
palindrome = false;
done = true;
}
//compare two characters
if(!((s.charAt(index))==s.charAt(s.length()-1-index))){
palindrome = false;
done = true;
} else index++;
if(index >=(s.length()-1-index))
done = true;
}
System.out.println("palindrome is " + palindrome) ; 

edit: removed check for even number of letters, not required.
[ August 12, 2008: Message edited by: Larry Frissell ]

[Campbell Ritchie]

 

Originally posted by K. Tsang:
I would have done it something like given string str is the input:

int midpoint=0;
char[] ary = str.toLowerCase().replaceAll(" ", "").toCharArray();
if(ary.size()%2 == 0) midpoint = ary.size()/2;
else midpoint = Integer.parseInt(ary.size()/2); //+1?
for(int i=0; i < midpoint; i++){
for(int j=ary.size(); j > midpoint; j--){
if(!ary[i].equals(ary[j])) Sytem.out.println("Not Palindrome"); break;
} }
System.out.println("Is Palindrome");

The !ary[i].equals(ary[j]) can be ary[i] != ary[j] for chars.

That will print

Not Palindrome
Is Palindrome

for a non-palindrome. And it won't compile if you try that parseInt() call. And you are calling an Object method on a char primitive; you must use the == and != operators for chars, not equals().

I have already said there is no need for the check whether you have an odd or even number of characters; the worst that can go wrong is that you compare the middle character to itself.
[ August 12, 2008: Message edited by: Campbell Ritchie ]

[Sagar Rohankar]

Had anybody tried it recursively ,

I tried but not succeed ,

class Palin
{
public static boolean isPalin(String str, int fwd, int bkwd)
{
if(str.charAt(fwd) == str.charAt(bkwd))
{
//System.out.println(true);
if(fwd <= last )
{
return true;
}
[B]return isPalin(str, ++fwd, --bkwd) ;[/B]
}
else
return false;
}
public static void main(String as[])
{
String s = "nitin";/*saippuakivikauppias*/
int len = s.length();
boolean isPal = true;
isPal = isPalin(s, 0, len-1);
System.out.println(isPal);
}
}

ya, This problem is not good for recursive program , still I tried it.
[The main gotcha is , How can we add the returned boolean results , like If later at bottom of call stack if it returns 'false', I want to add with the next upper call returned boolean ]

Any inputs ??
[ August 13, 2008: Message edited by: Sagar Rohankar ]

[Campbell Ritchie]

Of course you can design a recursive method; to return the combined boolean result, you use the conditional operators.

Just off the top of my head . . .

. . .
if (isPalindrome("Campbell", 0)
{
System.out.println("Palindrome.");
}
else
{
System.out.println("Not palidrome.");
}
. . .
public static boolean isPalindrome(String text, int i)
{
return i <= text.length() / 2
?
text.charAt(i) == text.charAt(text.length() - i - 1)
&& isPalindrome(text, i + 1)
:
true;
}

Try that, see whether it works.

[Sagar Rohankar]

It works great, You rocks Campbell !!

When I ll got those General computing neurons !

I tried my code in your way and I succeed !!

 public static boolean isPalin(String str, int fwd, int last)
{
if( fwd <= last )
{
return str.charAt(fwd) == str.charAt(last) && isPalin(str, ++fwd, --last) ;
}
return true;
} 

Thanks,

[Rob Spoor]

You can turn that guard into "fwd < last", since if fwd == last then str.charAt(fwd) == str.charAt(last) by definition.

[Sagar Rohankar]

 

Originally posted by Rob Prime:
You can turn that guard into "fwd < last", since if fwd == last then str.charAt(fwd) == str.charAt(last) by definition.

Thanks Rob, that's saved my whole one recursion !

O(n/2) - Average

[Nitin, If you are still following this thread , you come to know that How many answers you can get here, just you need to show your efforts first !]
[ August 13, 2008: Message edited by: Sagar Rohankar ]

[Rob Spoor]

 

Originally posted by Sagar Rohankar:
O(n/2) - Average

Which is still O(n), but I don't think you can get any better than that since you will have to inspect each character.

[Sagar Rohankar]

But don't you think , at the [worst, when string is palindrome ] case ,we are iterating for n/2 times.

Pl correct me If I`m wrong !
[ August 13, 2008: Message edited by: Sagar Rohankar ]

[Campbell Ritchie]

You are correct that you have n/2 repetitions (not called iterations if you use recursion), but the big-O notation calls that O(n) complexity. If you take a word twice as long, your program will run twice as long on average.

If a word is not however a palindrome, you might find a difference at the beginning and terminate the repetition earlier; both my suggested forms will do that.

I think I ought to take Rob's point about < and <=; I think I could have used < instead of <= too.

[K. Tsang]

Campbell, for my attempt I don't expect to check the midpoint value ... that's why it's > or < and not >= or <=.

OK after testing it I admit using the char array concept may not be the most effective and yes the midpoint variable is pointless. The println statement should have been a boolean value to false to break the loop.
[ August 13, 2008: Message edited by: K. Tsang ]

[Sagar Rohankar]

 

Originally posted by Campbell Ritchie:
You are correct that you have n/2 repetitions (not called iterations if you use recursion), but the big-O notation calls that O(n) complexity. If you take a word twice as long, your program will run twice as long on average.

So you mean that, the repetitions may be n/2 or n/4 , the complexity must be denoted by O(n) only ! I`m right ?

[Richard Bradford]

An alternative solution would be to reverse the string and compare with the original. Something along the lines of:

public boolean isPala(String test) {
boolean isPala = false;
char[] reverse = new char[test.length()];
char[] chars = test.toCharArray();
for (int i=test.length()-1, j=0; i>-1; i--,j++) {
reverse[j] = chars[i];
}
String revString = new String(reverse);
if (revString.equals(test)) {
isPala = true;
}
return isPala;
}

or

public static boolean isPala2(String test) {
boolean isPala = false;
String rev = new StringBuffer(test).reverse().toString();
if (rev.equals(test)) {
isPala = true;
}
return isPala;
}

[ August 14, 2008: Message edited by: Richard Bradford ]

[Campbell Ritchie]

 

Originally posted by Sagar Rohankar:
So you mean that, the repetitions may be n/2 or n/4 , the complexity must be denoted by O(n) only ! I`m right ?

Yes. Both instances are called linear complexity.

[Sagar Rohankar]

Ok, I got it !