Question

An English word is called palindrome if its meaning may be interpreted the same way in either forward or reverse direction. Some examples of common palindromic words: civic, radar, level, rotor, noon, etc.

Design an algorithm that takes a word as input and decides if the input word is palindrome. In your algorithm, a stack should be used. Describe the pseudo-code of your algorithm. What is the time complexity of your algorithm in big-O?

PLEAS USE PSEUDO-CODE.

Answer 1

pseudocode -

1. read the word
2. len=length(word)
3. declare stack S
4. for i=0 to len
   S.push(word[i])
5. end loop with variable i
6. for i=0 to len
   ch=s.top()

s.pop()
   if ch equals word[i]
       continue
   else
       print("Not palindrome")
       exit()
7. end loop with variable i
8. print("Palindrome")

Time complexity -

We are traversing the string once calculating its length, then pushing elements to the stack and once popping out the elements from the stack.

And we are also traversing stack once.

So time complexity = (O(n+n+n+n))= O(4*n)= O(n), where n is the length of the string

And we are using stack too, so space complexity = O(n)

c++ code -

#include<bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
   string word;
   cout<<"Enter word"<<endl;
   cin>>word;
   int l=word.size();
   stack<char> s;
   for (int i = 0; i < l; ++i)
   {
       s.push(word[i]);
   }
   for (int i = 0; i < l; ++i)
   {
       char ch=s.top();
       s.pop();
       if (ch==word[i])
       {
           continue;
       }
       else
       {
           cout<<"Not palindrome"<<endl;
           exit(0);
       }
   }
   cout<<"palindrome"<<endl;
   return 0;
}
output-

Enter word
civik
Not palindrome

output -

Enter word
civic
palindrome