Question

4. A English word is palindrome if its characters read the same backward as forward. For example, civic is palindrome. Describe a recursive algorithm for determining a word w of length n is palindrome or not. Analyze its time complexity using a recursion tree. Implement your algorithm in Java

Answer 1

Algorithm:

def isPalRec(st, s, e) : 
      
    # If there is only one character 
    if (s == e): 
        return True
  
    # If first and last 
    # characters do not match 
    if (st[s] != st[e]) : 
        return False
  
    # If there are more than  
    # two characters, check if  
    # middle substring is also  
    # palindrome or not. 
    if (s < e + 1) : 
        return isPalRec(st, s + 1, e - 1); 
  
    return True
  
def isPalindrome(st) : 
    n = len(st) 
      
    # An empty string is  
    # considered as palindrome 
    if (n == 0) : 
        return True
      
    return isPalRec(st, 0, n - 1); 

Implementation

package learning;

import java.util.*; 
  
class Main
{ 
    // A recursive function that  
    // check a str(s..e) is  
    // palindrome or not. 
    static boolean isPalRec(String str,  int s, int e) 
    { 
        // If there is only one character 
        if (s == e) 
            return true; 
  
        // If first and last  
        // characters do not match 
        if ((str.charAt(s)) != (str.charAt(e))) 
            return false; 
  
        // If there are more than  
        // two characters, check if 
        // middle substring is also 
        // palindrome or not. 
        if (s < e + 1) 
            return isPalRec(str, s + 1, e - 1); 
  
        return true; 
    } 
  
    static boolean isPalindrome(String str) 
    { 
        int n = str.length(); 
  
    // An empty string is  
    // considered as palindrome 
        if (n == 0) 
            return true; 
  
        return isPalRec(str, 0, n - 1); 
    } 
  
    // Driver Code 
    public static void main(String args[]) 
    { 
        String str = "civic"; 
        
        System.out.print("Is " + str + " Palindrome: ");
        if (isPalindrome(str)) 
            System.out.println("Yes"); 
        else
            System.out.println("No"); 
        
        str = "ViVi";
        
        System.out.print("Is " + str + " Palindrome: ");
        if (isPalindrome(str)) 
            System.out.println("Yes"); 
        else
            System.out.println("No"); 
    } 
} 

OUTPUT: