Check if Substrings are palindrome

Given a string and several queries on substrings of the given input string, check whether the substring is a palindrome or not.

Approach 1:

Simplest approach is to get the substring and check if the substring is palindrome or not. This can be done directly checking each character with its reverse position. 

This way you will have to check palindrome for all the input queries.

Approach 2:

We can find out all the palindrome in the string using dynamic programming in o(n^2) complexity and then use the DP solution return result for each query.   

To find out if string is palindrome we will follow below method:

• String with size 1 is palindrome
• String with size 2 is palindrome if both characters are same
• String with size 3 or more is the palindrome if characters in between are a palindrome.

Solution below implements the approach 2:

import java.util.Scanner;

public class Palindrome {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();

        int queryI = sc.nextInt();
        int queryJ = sc.nextInt();

        int length = str.length();

        boolean[][] dp = new boolean[length][length];

        for (int diff = 0; diff < str.length(); diff++) {
            for (int i = 0, j = diff; j < str.length(); i++, j++) {
                switch (diff) {
                    case 0:
                        dp[i][j] = true;
                        break;
                    case 1:
                        dp[i][j] = str.charAt(i) == str.charAt(j);
                        break;
                    default:
                        dp[i][j] = dp[i + 1][j - 1] && str.charAt(i) == str.charAt(j);
                        break;
                }
            }
        }

        System.out.println("Substring from " + queryI + " to " + queryJ + " is palindrome : "  + dp[queryI][queryJ]);
    }
}

Comments are welcome.