CODEWITHSUNDEEP
javastring
user6622569
user6622569

Reputation: 75

Queries on subsequence of string

Given a string S and Q queries, each query contains a string T. The task is print “Yes” if T is subsequence of S, else print “No”. I am trying to learn algorithms and implementing them. I have written the below code in Java :

import java.util.Stack;

public class QueriesOnStringSubsequence {
    public boolean subSequence(String original, String query) {
        Stack<Character> s1 = new Stack<Character>();
        Stack<Character> s2 = new Stack<Character>();

        for (int i = 0; i < original.length(); i++) {
            s1.push(original.charAt(i));
            System.out.println(s1.peek());
        }
        for (int i = 0; i < query.length(); i++) {
            s2.push(query.charAt(i));
            System.out.println(s2.peek());
        }
        while (!s1.isEmpty() || !s2.isEmpty()) {
            Character s1Top = s1.peek();
            Character s2Top = s2.peek();
            if (s1Top == s2Top) {
                s1.pop();
                //System.out.println(i);
                s2.pop();
                return true;
            }
            System.out.print("True");
        }
        System.out.print("False");
        return false;
    }

    public static void main(String[] args) {
        QueriesOnStringSubsequence ob = new QueriesOnStringSubsequence();
        ob.subSequence("geeksforgeeks", "gg");
    }
}

I tried to debug this and in Eclipse and it won't go into the if condition. Can someone please explain where I am going wrong.

Upvotes: 1

Views: 177

Answers (2)

Mr. Polywhirl
Mr. Polywhirl

Reputation: 48693

As duncan pointed out, a stack may not be the best data structure for this. I assume you want to go in order which means that you should use a queue.

Here is an implementation. I used better variable naming conventions which help not only in readability, but also debugging.

import java.util.*;

public class QueriesOnStringSubsequence {
    public static void subSequence(String original, String query) {
        Queue<Character> originalQueue = stringToQueue(original);
        Queue<Character> queryQueue = stringToQueue(query);

        while (!originalQueue.isEmpty() && !queryQueue.isEmpty()) {
            Character originalQueueHead = originalQueue.peek();
            Character queryQueueHead = queryQueue.peek();

            if (originalQueueHead.equals(queryQueueHead)) {
                queryQueue.poll();
                System.out.print("YES");
            } else {
                System.out.print("NO");
            }

            originalQueue.poll();
            System.out.print("...");
        }
    }

    private static Queue<Character> stringToQueue(String input) {
        Queue<Character> queue = new LinkedList<Character>();
        for (int i = 0; i < input.length(); i++) {
            queue.add(input.charAt(i));
        }
        return queue;
    }

    public static void main(String[] args) {
        QueriesOnStringSubsequence.subSequence("geeksforgeeks", "gg");
    }
}

YES...NO...NO...NO...NO...NO...NO...NO...YES...

Upvotes: 0

duncan
duncan

Reputation: 1161

Keep in mind that Stack are LIFO data structures.

This means when you run:

Character s1Top = s1.peek();
Character s2Top = s2.peek();

You are getting the last two characters added. In this case s and g.

This means that the if statement will not be met. The second time the software loops since you are using Stack.peek the element is looked at but not changed. Therefore your while loop is looking at s and g over and over. Since they are never equal your if will never be met and therefore your while loop will be infinite.

Also you are checking:

while(!s1.isEmpty() || !s2.isEmpty())

This means both need to be empty before exiting which can cause an issue. I believe you want to use:

while(!s1.isEmpty() && !s2.isEmpty())

Upvotes: 1

Related Questions