java - 字符串子序列的查询

Question

给定一个字符串 S 和 Q 查询，每个查询包含一个字符串 T。任务是如果 T 是 S 的子序列则打印“Yes”，否则打印“No”。我正在尝试学习算法并实现它们。我用 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");
    }
}

我尝试在 Eclipse 中调试它，但它不会进入 if 条件。有人可以解释一下我哪里出了问题吗？

Answer 1

请记住，Stack 是 LIFO 数据结构。

这意味着当你运行时:

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

您将添加最后两个字符。在本例中，s 和 g。

这意味着 if 语句将不会得到满足。自从您使用 Stack.peek 以来，软件第二次循环时，会查看该元素，但不会更改该元素。因此，您的 while 循环会一遍又一遍地查看 s 和 g 。由于它们永远不相等，因此您的 if 永远不会被满足，因此您的 while 循环将是无限的。

您还在检查:

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

这意味着在退出之前两者都需要为空，这可能会导致问题。我相信您想使用:

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