2
\$\begingroup\$

Valid Alphanumeric Palindrome

Problem (from Leetcode)

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, A man, a plan, a canal: Panama is a palindrome but race a car is not a palindrome.

Discussion

My approach was the following:

  1. Start with first and last characters of the input string (keeping track of their respective indices).
  2. While the index of the first character is less than the index of it's "opposite" character... a. For both characters, increment / decrement their index if they're not alphanumeric (and first character index is less than it's opposite character index b. The invalid case occurs when
    1. The first character index is less than it's opposite
    2. Both characters are not alphabetic or not numeric
    3. Both characters are alphabetic and their lower case (or upper case) values are not equal
    4. Both characters are numeric but their values are not equal c. Increment the first character index and decrement the opposite character index
  3. If able to exit the while loop, return true

Other discussion points

  • I could probably make the helper methods (like isAlphanumeric) private
  • Open to other (better) names
  • My if statement is pretty inelegant / hard to read - move to a helper method perhaps?
  • Convert the whiles to fors with conditionals?

Implementation

public class AlphanumericPalindromeValidator {
    public static boolean isValid(String value) {
        char[] chars = value.toCharArray();
        int i = 0;
        int j = value.length() - 1;
        while (i < j) {
            char character = chars[i];
            while (!AlphanumericPalindromeValidator.isAlphanumeric(character) && i < j) {
                i++;
                character = chars[i];
            }
            char oppositeCharacter = chars[j];
            while (!AlphanumericPalindromeValidator.isAlphanumeric(oppositeCharacter) && i < j) {
                j--;
                oppositeCharacter = chars[j];
            }

            if (i < j
                    && !(AlphanumericPalindromeValidator.isAlphabeticCharacterPair(character, oppositeCharacter)
                        && Character.toLowerCase(character) == Character.toLowerCase(oppositeCharacter))
                    && !(AlphanumericPalindromeValidator.isNumericCharacterPair(character, oppositeCharacter)
                        && character == oppositeCharacter)) {
                return false;
            }

            i++;
            j--;
        }

        return true;
    }

    public static boolean isAlphanumeric(char c) {
        return Character.isAlphabetic(c) || Character.isDigit(c);
    }

    public static boolean isAlphabeticCharacterPair(char c1, char c2) {
        return Character.isAlphabetic(c1) && Character.isAlphabetic(c2);
    }

    public static boolean isNumericCharacterPair(char c1, char c2) {
        return Character.isDigit(c1) && Character.isDigit(c2);
    }
\$\endgroup\$
2
\$\begingroup\$

Code style

  • Definitely make the helper methods private;
  • There is no need to specify the class name when calling a static method in the same call. Instead of AlphanumericPalindromeValidator.isNumericCharacterPair(), just call isNumericCharacterPair();
  • Do a static import of the static methods of Character;
  • There is no need for the variables oppositeCharacter and character. Only keep them if it helps you make the code easier to read.
  • it's possible to make the inner while loop a one liner with a for, but I actually think the while better expresses what is the intent in this case.

If condition

I don't see the point of the first check: i < j. At ths point you know that i<=j. If i == j, the comparison will succeed. This is the case of palindromes with an odd length.

You don't need to check if the char is alphabetic to use Character.toLowerCase(). The method will simply return the same char if there is no mapping to lower case for a given char.

You can also use Character.isLetterOrDigit instead of your isAlphanumeric, unless you care about the subtle differences between "alphatetic" and "letter".

Suggested solution

No helper methods are needed.

public static boolean isValid(String value) {
  char[] chars = value.toCharArray();
  int i = 0;
  int j = value.length() - 1;

  while (i < j) {
    while (!isLetterOrDigit(chars[i]) && i < j) {
      i++;
    }
    while (!isLetterOrDigit(chars[j]) && i < j) {
      j--;
    }

    if (Character.toLowerCase(chars[i]) != toLowerCase(chars[j])) {
      return false;
    }

    i++;
    j--;
  }
  return true;
}
\$\endgroup\$
  • \$\begingroup\$ ---The point of the i < j check is for the case where the string is comprised of only non-alphanumeric characters.--- Nope, I'm wrong. \$\endgroup\$ – Jae Bradley Nov 5 '17 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.