Question

Write a method public static boolean isPalindrome(String input) that uses one or more stacks to determine if a given string is a palindrome. [A palindrome is a string that reads the same forwards and backwards, for example ‘racecar’, ‘civic’]. Make sure that your method works correctly for special cases, if any.

(b) What is the big-O complexity of your method in terms of the list size n.

Answer 1

Java Code:

import java.util.*;

class Main {

public static boolean isPalindrome(String input){

Stack st=new Stack();

for(int i=0;i<input.length();i++) {

st.push(input.charAt(i));

}

String rev="";

while (!st.isEmpty()) {

rev=rev+st.pop();

}

if(input.equals(rev))

return true;

else

return false;

}

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

String input=new String();

System.out.print("Enter a string: ");

input=sc.nextLine();

if(isPalindrome(input))

System.out.println("String is a palindrome");

else

System.out.println("String is not a palindrome");

}

}

b)The time complexity of the function is O(n) where n is the input string size, because there are two loops in function for loop runs n times and while loop also run n times, so total time is 2n so time commplexity = O(2n) =O(n).

if you like the answer please provide a thumbs up.