detecting palindromes

[Jeremy Wages]

Hello again,  I was given this assignment:
For this week's lab we will be creating two separate methods to detect if a user entered string is a palindrome. The first method should ONLY use the string class and/or character class and should compare one character at a time working from the outside in.

The second method should use the StringBuilder class and can use any method of that class.

Note: Special characters, character case, and spaces should be ignored.

I had to do some googling to get an algorithm for the first part of the assignment (using either the character class or string class), but I also want to understand whats happening.  Can you help me understand?

for (int i = 0; i < (n / 2); i++) {
			if (str.charAt(i) != str.charAt(n - i - 1)) {
				System.out.println(str + " is not a palindrome.");
				break;
			} else {
				System.out.println(str + " is a palindrome!");
				break;
			}
		}
	}

[Jeremy Wages]

if (str.charAt(i) != str.charAt(n - i - 1))

is this checking if first letter == the last letter, 2nd letter == 2nd to last letter, etc?

Also,  I interpreted "Note: Special characters, character case, and spaces should be ignored."  As in I don't have to worry about account for/checking for (.equalsIgnoreCase() ) and he'll only use one word palindromes to check it?

[Carey Brown]

Jeremy Wages wrote:

if (str.charAt(i) != str.charAt(n - i - 1))

is this checking if first letter == the last letter, 2nd letter == 2nd to last letter, etc?

Also,  I interpreted "Note: Special characters, character case, and spaces should be ignored."  As in I don't have to worry about account for/checking for (.equalsIgnoreCase() ) and he'll only use one word palindromes to check it?

I don't think you interpreted that correctly. I think it's up to you to ignore those characters and case.

[Henry Wong]

Jeremy Wages wrote:
I had to do some googling to get an algorithm for the first part of the assignment (using either the character class or string class), but I also want to understand whats happening.  Can you help me understand?

The way this question is worded, it seems to imply that you got a working example from the internet -- and is having trouble understanding it.  Question. Does it actually work? ... meaning have you tested it with some example data?

Henry

[Jeremy Wages]

Henry Wong wrote:

Jeremy Wages wrote:
I had to do some googling to get an algorithm for the first part of the assignment (using either the character class or string class), but I also want to understand whats happening.  Can you help me understand?

The way this question is worded, it seems to imply that you got a working example from the internet -- and is having trouble understanding it.  Question. Does it actually work? ... meaning have you tested it with some example data?

Henry

I have tested it and it seems to work.

[Carey Brown]

Look closely at the if/else logic. IF it's true print and break, ELSE print and break. In both cases you break out of the loop. What happens when you try to compare the second to the second to last characters?

[Mel Reams]

When I come across an algorithm I don't understand, I like to make the computer tell me what it's doing More precisely, I would put a System.out.println() in for pretty much every step - how many times you've gone through the loop, what the index of the first character you're looking at is, what the index of the second character is, what character the first character actually is, and what character the second character is.

Does that make sense? I can give you some example code if not.

[Jeremy Wages]

Ah, yeah, doesn't work anymore.  

[Jeremy Wages]

I take that back, it seems to work, but prints out every iteration.

[Mel Reams]

Huh. From the code you posted at the beginning, I was expecting you to say "uh oh, it only prints out 1 iteration of the loop and decides from that 1 comparison whether or not the string is a palindrome." Is the code you're running exactly what you put in your first post?

[Jeremy Wages]

I've changed it now so it prints correctly, but everything is the same except I added the boolean and extra if/else statements for printing.

import java.util.Scanner;

public class Palindrome {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);

		System.out.println("Enter a string: ");
		String str = input.nextLine();
		int n = str.length();

		boolean isPalindrome = false;
		for (int i = 0; i < (n / 2); i++) {
			if (str.charAt(i) != str.charAt(n - i - 1)) {
				isPalindrome = true;
			} else {
				isPalindrome = false;
			}

		}
		if (isPalindrome) {
			System.out.println(str + " is not a palindrome.");
		} else {
			System.out.println(str + " is a palindrome!");
		}
	}
}

[Jeremy Wages]

I guess I should've posted the whole thing from the get-go.  Sorry!

[Mel Reams]

Hey, now you know Fiddly little details like *exactly* what code you're running are really important, programming is basically all fiddly little details.

Do you feel comfortable with what the algorithm is doing now that you made it print everything out? If so we can start talking about how to modify your code to ignore special characters and anything else you want to leave out.

[Jeremy Wages]

Yes. We can talk about that. If I fall asleep I'll get back here tomorrow.

[Henry Wong]

Okay, I might be sounding like a broken record, but...

Henry Wong wrote:
Question. Does it actually work? ... meaning have you tested it with some example data?

Admittedly, you will need to try a bit harder with your new code to break it though...

Henry

[Mel Reams]

No worries, I'm going to have to go to sleep before long too.

The thing with ignoring some characters is that there's a terrible way to do it and an easy way to do it. The terrible way is to look at each character and see if it's a special character or a space or punctuation or anything and ignore it and take the next character if it is. That will make a serious mess of your loop.

The easy way is to ignore all the stuff you don't want up front - that is, make a copy of your input string and strip out all the stuff you don't want. The tricky part there is making a list of everything you don't want - there are so many different special characters out there. It's a lot easier if you do the opposite.

[Campbell Ritchie]

Mel Reams wrote:. . . The tricky part there is making a list of everything you don't want . . . It's a lot easier if you do the opposite.

You mean making a list of the characters you do want? Since there are only 26 of them, that shou‍ld be easy enough. That would match the customary conventions about palindromes where

Madam, I'm Adam.

...is usually considered a palindrome minus the space comma apostrophe and full stop, and case‑insensitive.

[Junilu Lacar]

Look at the JavaDocs for java.lang.Character to see which of its methods are useful for this. There are a number of utility methods that check for the type of character you have.

[Jeremy Wages]

Mel Reams wrote:No worries, I'm going to have to go to sleep before long too.

The thing with ignoring some characters is that there's a terrible way to do it and an easy way to do it. The terrible way is to look at each character and see if it's a special character or a space or punctuation or anything and ignore it and take the next character if it is. That will make a serious mess of your loop.

The easy way is to ignore all the stuff you don't want up front - that is, make a copy of your input string and strip out all the stuff you don't want. The tricky part there is making a list of everything you don't want - there are so many different special characters out there. It's a lot easier if you do the opposite.

Like Campbell said focus on the things I do want to compare.  So like, only if 'i' is a letter.  Maybe the isLetter() method?

[Junilu Lacar]

Jeremy Wages wrote:Maybe the isLetter() method?

Don't ask us, try it out yourself.

[Jeremy Wages]

I'll try something like this when I get home ;)

for (int i = 0; i < (n / 2); i++) {
            if (isLetter(str.charAt(i)) == isLetter(str.charAt(n - i - 1))) {
                isPalindrome = true;
            } else {
                isPalindrome = false;
            }
 
        }

[Knute Snortum]

If you input "Ab cba", it will say this is not a palindrome.  The reason it fails can be discerned by entering a few well placed System.out.println() statements.  You may also want to switch the true/false values of isPalindrome so that it is more intuitive.

If you need another hint, read on.

Should the loop continue if the string is found to not be a palindrome?

[Campbell Ritchie]

Have you explored the isLetter method?

[Campbell Ritchie]

Jeremy Wages wrote:. . .

for (int i = 0; i < (n / 2); i++) {
            if (isLetter(str.charAt(i)) == isLetter(str.charAt(n - i - 1))) {
                isPalindrome = true;
            } else {
                isPalindrome = false;
            }
 
        }

Don't write
if (x) y = true; else y = false;
As you will see in the old Sun style guide, that can simply be written as
y = x;
I suggest you add && and isPalindrome to the continuation condition in that for loop. That will terminate your loop at the appropriate moment. I suggest you also try to work out why line 2 in that code will give you the wrong answer.

[Jeremy Wages]

Campbell Ritchie wrote:Have you explored the isLetter method?

I have glanced at it, but I'll look more closely this afternoon after work.  I'm thinking what I posted wont work.

[Campbell Ritchie]

Jeremy Wages wrote:. . .  I'm thinking what I posted wont work.

I appear to have posted < 1″ before you.

No, it won't work.

[Jeremy Wages]

Campbell Ritchie wrote:

Jeremy Wages wrote:. . .  I'm thinking what I posted wont work.

I appear to have posted < 1″ before you.

No, it won't work.

I'll have to use a boolean, yeah?  In my head I'm not sure how I'd set it up, cos if it's not a letter, then I'd want it to skip that and compare the next one.  

[Campbell Ritchie]

Go back and read the whole of the thr‍ead; you were given some good advice (I think yesterday) which you appear to have missed.

[Jeremy Wages]

Campbell Ritchie wrote:

Don't write
if (x) y = true; else y = false;
As you will see in the old Sun style guide, that can simply be written as
y = x;
I suggest you add && and isPalindrome to the continuation condition in that for loop. That will terminate your loop at the appropriate moment. I suggest you also try to work out why line 2 in that code will give you the wrong answer.

I just saw this.  I'll take that into consideration.  I must be dense though, cos I can't find the advice mentioned earlier that I seemed to have missed.

[Jeremy Wages]

Henry Wong wrote:
Okay, I might be sounding like a broken record, but...

Admittedly, you will need to try a bit harder with your new code to break it though...

Henry

I can get it to not work with spaces, characters, numbers, etc.  Trying to work out how to ignore those now.

[Campbell Ritchie]

Jeremy Wages wrote:. . . I can't find the advice mentioned earlier that I seemed to have missed.

Look where Mel Reams said there is a hard way and an easy way.

[Jeremy Wages]

Campbell Ritchie wrote:

Jeremy Wages wrote:. . . I can't find the advice mentioned earlier that I seemed to have missed.

Look where Mel Reams said there is a hard way and an easy way.

That's where I was trying to go with the isLetter(). I just have to figure out the right way.

[Campbell Ritchie]

Doesn't his post give you any hints about which the easy way is?

[Jeremy Wages]

Campbell Ritchie wrote:Doesn't his post give you any hints about which the easy way is?

I didn't account for the part about making a copy of the string and "extracting" what I want.  So what I want to do is make a copy of the string and pull out all of the letters.

[Jeremy Wages]

import java.util.Scanner;

public class Palindrome {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);

		System.out.println("Enter a string: ");
		String str = input.nextLine();
		
		String newString = str.replaceAll("[^a-zA-z]+", "");
		int n = newString.length();
		
		boolean isPalindrome = false;
		for (int i = 0; i < (n / 2); i++) {
			if (newString.charAt(i) == newString.charAt(n - i - 1)) {
				isPalindrome = true;
			} else {
				isPalindrome = false;
			}
		}
		if (isPalindrome) {
			System.out.println(str + " is a palindrome!");
		} else {
			System.out.println(str + " is not a palindrome.");
		}
	}
}

I'll admit I had to google "how to extract only letters from a string" to come up with [^a-zA-z]+.  How else would I have come up with it (not rhetorical)?  Like if I didn't have access to google, would it just be familiarity with the syntax and general knowledge?  I read about replaceAll() on the oracle website, but I didn't see anything like that.  I experimented with it, and if I remove the carrot (^) it only prints out those characters that aren't a letter.  So the carrot is saying, keep the letters?  Also, I'm not sure if the + even does anything cos it prints out the same with it there or without it.  

Campbell Ritchie, now I'm trying to incorporate your suggestion with the old Sun style guide.  I'm not 100% how to go about it, but I'm sure its something simple that I'm missing.

[Jeremy Wages]

Ugh, I even used the buttons instead of typing

myself and I still messed it up.

[Mel Reams]

Jeremy Wages wrote:I'll admit I had to google "how to extract only letters from a string" to come up with [^a-zA-z]+.  How else would I have come up with it (not rhetorical)?  Like if I didn't have access to google, would it just be familiarity with the syntax and general knowledge?

Excellent, you got it! And that's a really good question. Honestly a lot of it is familiarity with programming in general. String manipulation with regexs is a really common thing to need to do, so just about every language gives you some way to do it. Once you know that regexs are a thing, you can google for the details of using them in the language you're working in. You can also get quite a ways with just the java api docs if, for example you had a copy of those saved but didn't have google. Reading them is not super interesting I will freely admit, but if you were to look over the methods in the String class you would eventually find replaceAll and in the details of that method there's a link to Pattern.

That question is also why I was being a bit vague and mysterious when I was hinting about how you should solve the problem - if I just tell you the answer then you don't learn nearly as much and I want to actually help, not leave you in a position where you can't do it without us.

[Jeremy Wages]

Mel Reams wrote:
That question is also why I was being a bit vague and mysterious when I was hinting about how you should solve the problem - if I just tell you the answer then you don't learn nearly as much and I want to actually help, not leave you in a position where you can't do it without us.

I have no problem with the help I get being vague.  I actually want to learn as well, so it helps!

Is this how I'd do it with a stringbuilder?  Or is there a more efficient way (it works the way I did it).

import java.util.Scanner;

public class Palindrome2 {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);

		System.out.println("Enter a string: ");
		String str = input.nextLine();
		StringBuilder sb = new StringBuilder(str.replaceAll("[^a-zA-Z]", ""));
		str = str.replaceAll("[^a-zA-z]", "");
		
		
		if (sb.reverse().toString().equalsIgnoreCase(str)) {
			System.out.println(str + " is a palindrome!");
		} else {
			System.out.println(str + " is not a palindrome.");
		}
	}

[Campbell Ritchie]

Jeremy Wages wrote:

import java.util.Scanner;

public class Palindrome {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);

		System.out.println("Enter a string: ");
		String str = input.nextLine();
		
		String newString = str.replaceAll("[^a-zA-z]+", "");
		int n = newString.length();
		
		boolean isPalindrome = false;
		for (int i = 0; i < (n / 2); i++) {
			if (newString.charAt(i) == newString.charAt(n - i - 1)) {
				isPalindrome = true;
			} else {
				isPalindrome = false;
			}
		}
		if (isPalindrome) {
			System.out.println(str + " is a palindrome!");
		} else {
			System.out.println(str + " is not a palindrome.");
		}
	}
}

. . .

No, that won't work. You can write something like Madam and have it show correctly as a palindrome, but that will also show Saddam as a palindrome. [Actually it won't, because of the capital letters, but there is an easy way to correct that.] That is because it is only testing one pair of letters and not taking any action when you get false. I think I shall have to let you out of your misery. Instead of lines 13‑20, write this:boolean isPalindrome = true; // don't start with false for (int i = 0; isPalindrome && i < myString.length() / 2; i++) {   isPalindrome = ??? }You need to start with true otherwise the loop will never start. I like to use characteristics of objects in loops rather than separate variables. If your predicate is false, you terminate the loop at that point. I challenge you to reduce lines 21‑25 to one line with the ?: operator. It is probably easier with printf than println.
Your technique with a StringBuulder will work, but you don't need both replace calls.

[Jeremy Wages]

It's unfortunate that I didn't catch that.  It seemed to work with what I was entering, including "Madam, I'm Adam.".  I'll accept your challenge and see what I can do this afternoon.  

For the stringbuilder, I couldn't get it to work properly without calling replace all on the entered string as well (I did create a copy of "str", but it was after I posted it.)