Working with palindromes

[Waseemn]

Hello All,

OK I am not sure if any of you here are also coming from the C++ forum, but I finished my C++ class, got an A, thanks to all your help, and now I am onto Java.

I am still a beginner in both Java and C++ and there is more work ahead of me to finally know enough to be able to effectively participate in these fora.

For now, the Java class requires us to write a program that will determine if a string is a palindrome or not.

My theory/approach is:

Get the string from the user.

Check if it has an even number of characters or an odd number of characters using the Mod % operand. If it has an odd number of characters then I will have what I call a pivot character where by what is on the left of this character is equal to what is on the right, and I can discard the pivot character.
Split the string into the two parts on either side of the pivot. If even, then I will have equal sides, so the division will happen without discarding any characters.

Now here comes the question(s):

Should I reverse one part and check if it is equal to the other part, this will require a For loop which might take time, and then simply say if FirstPartString Isequal(LastPartString) = TRUE then we have a palindrome.

Or

Simply compare the two parts of the string going backwards, so character at index 0 will be compared to character at index String.Lenghth(); which will also require a For loop, but will eliminate the equality check step. Once I find a character that is not the same, boom, exit loop and announce that it is not a palindrome.

What is the most efficient way to do this kind of an assignment? No arrays can be used since we did not cover arrays so far.

Also, should I eliminate the spaces between the words, and match up the characters, because some times the spaces do come in the way. If so, what is the best way to remove the white space from a sting? ReplaceAll will have to go character by character, and that is IMHO slow. Any suggestions?

Thanks

Waseemn

[Alex Edwards]

Hello All,

OK I am not sure if any of you here are also coming from the C++ forum, but I finished my C++ class, got an A, thanks to all your help, and now I am onto Java.

I am still a beginner in both Java and C++ and there is more work ahead of me to finally know enough to be able to effectively participate in these fora.

For now, the Java class requires us to write a program that will determine if a string is a palindrome or not.

My theory/approach is:

Get the string from the user.

Check if it has an even number of characters or an odd number of characters using the Mod % operand. If it has an odd number of characters then I will have what I call a pivot character where by what is on the left of this character is equal to what is on the right, and I can discard the pivot character.
Split the string into the two parts on either side of the pivot. If even, then I will have equal sides, so the division will happen without discarding any characters.

Now here comes the question(s):

Should I reverse one part and check if it is equal to the other part, this will require a For loop which might take time, and then simply say if FirstPartString Isequal(LastPartString) = TRUE then we have a palindrome.

Or

Simply compare the two parts of the string going backwards, so character at index 0 will be compared to character at index String.Lenghth(); which will also require a For loop, but will eliminate the equality check step. Once I find a character that is not the same, boom, exit loop and announce that it is not a palindrome.

What is the most efficient way to do this kind of an assignment? No arrays can be used since we did not cover arrays so far.

Also, should I eliminate the spaces between the words, and match up the characters, because some times the spaces do come in the way. If so, what is the best way to remove the white space from a sting? ReplaceAll will have to go character by character, and that is IMHO slow. Any suggestions?

Thanks

Waseemn

Remember that even strings/values can be split in half perfectly. You'll have to find a way to ignore the middle character in odd strings. You'll most likely want to make a method like this that determines if a String is a palindrome or not--

public static boolean isPalindrome(String arg)
{
        //code that determines the length of the String and performs some functionality

       //code that checks the characters        

       
        //returns the state of whether the String is a palindrome or not.
        return false; //stub

}

--Here are some hints for you.

You can eliminate your odd vs even number by doing something like this--

// within method isPalindrome
String value = new String(arg); //allocates memory for a new String object that has arg's chars
int parse = (value.length()/2); //int division
int match = 0;

if(!(value.length()%2 == 0)) //if the String consists of an odd number of chars...
{
       value.charAt(parse) = " "; //give the middle char a space value
       value.replace("", " "); //replaces the space value with a closed string
       //String should now be an even number
}
for(int i = 0; i < parse; i++)
{
       if(value.charAt(i) == value.charAt(value.length() - i))
           match++;
}

return match == parse;

--notice I didn't compile or do any real checks with this code. It may or may not work.

If you look at the String class in the Java.lang API you will see that it consists of many useful operations for Strings.

[Alex Edwards]

I just noticed this but for the above code line 15 should be--

if(value.charAt(i) == value.charAt((value.length() - 1) - i))

[stephen84s]

How about comparing the string directly with its reverse,
You howvere will need to use the StringBuffer if you want to reverse a string directly and then directly compare it the original string.

I donno but somehow I feel its too easy to be true ?

[Alex Edwards]

How about comparing the string directly with its reverse, , I donno but somehow I feel its too easy to be true ?

You probably could - that would work.

It would be far better than the example above or any bitshifting/XORing/bitwise ANDing

[Alex Edwards]

I found this way easy to understand --

public class String_Manip{

	public static void main(String[] args){

		System.out.println(isPalindrome("mom")); // odd
		System.out.println(isPalindrome("dad")); // odd
		System.out.println(isPalindrome("toot")); // even
		System.out.println(isPalindrome("son")); // not palindrome
		System.out.println(isPalindrome("daughter")); // not palindrome
	}

	public static boolean isPalindrome(String arg){

		int matches = 0, splitValue = arg.length()/2;

		for(int i = 0; i < splitValue; i++){
			if(arg.charAt(i) == arg.charAt((arg.length() - 1) - i))
				matches++;
		}
		return matches == splitValue;
	}
}

--I'll look into StringBuffer though, sounds interesting.

Edit - here's a better version that takes into account uneven letters --

public class String_Manip{

	public static void main(String[] args){

		System.out.println(isPalindrome("Mom")); // odd
		System.out.println(isPalindrome("dad")); // odd
		System.out.println(isPalindrome("toot")); // even
		System.out.println(isPalindrome("son")); // not palindrome
		System.out.println(isPalindrome("daughter")); // not palindrome
	}

	public static boolean isPalindrome(String arg){

		int matches = 0, splitValue = arg.length()/2;

		for(int i = 0; i < splitValue; i++){
			if((Character.toUpperCase(arg.charAt(i)) == arg.charAt((arg.length() - 1) - i))
			|| (Character.toLowerCase(arg.charAt(i)) == arg.charAt((arg.length() - 1) - i)))
				matches++;
		}
		return matches == splitValue;
	}
}