CodingGyan

Valid Palindrome (Ignore Symbols and Case)

easy Strings

Problem

Read one line. Keep only letters and digits, treat upper and lower case as the same, and check if the result reads the same forward and backward. Print true or false.

Constraints

  • 0 <= length <= 10^5, ASCII text

Examples

Input

A man, a plan, a canal: Panama

Output

true

Solutions

Best approachTime O(n)Space O(1)

Two pointers move from both ends to the middle. They skip symbols and compare the letters in lower case. No extra string is built, so the extra memory is O(1).

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Palindrome check that ignores symbols.
 * Input   : One line of text.
 * Output  : true or false.
 * Approach: Use two pointers.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static boolean solve(String s) {
        // Step 1: Two pointers. One starts at the left end and one at the right end.
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            // Step 2: Skip characters that are not letters or digits.
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }

            // Step 3: Compare both characters in lower case. A difference means: not a palindrome.
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }

            // Step 4: Move both pointers to the middle.
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.hasNextLine() ? scanner.nextLine() : "";
        System.out.println(solve(s));
    }
}
Hints (1)
  1. Which characters should be skipped?

Try these next