Abfragen auf Teilfolge von Zeichenfolge

Question

Bei einer Zeichenfolge S und Q-Abfragen enthält jede Abfrage eine Zeichenfolge T. Die Aufgabe wird "Ja" gedruckt, wenn T Teilfolge von S ist, andernfalls "Nein" drucken. Ich versuche, Algorithmen zu lernen und sie zu implementieren. Ich habe den Code unten in Java geschrieben:

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"); 
    } 
} 

Ich habe versucht, diese und in Eclipse zu debuggen und es wird nicht in den Zustand, wenn gehen. Kann mir bitte jemand erklären, wo ich falsch liege?

Answer 1

Beachten Sie, dass Stack LIFO-Datenstrukturen sind. Das bedeutet,

, wenn Sie laufen:

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

Sie sind die letzten zwei Zeichen hinzugefügt bekommen. In diesem Fall s und g.

Dies bedeutet, dass die if Anweisung nicht erfüllt wird. Das zweite Mal, dass die Software Loops verwendet, da Sie Stack.peek verwenden, wird das Element betrachtet, aber nicht geändert. Daher sieht Ihre while Schleife s und g immer wieder. Da sie niemals gleich sind, wird Ihre if niemals erfüllt sein und daher wird Ihre while Schleife unendlich sein.

Auch Sie überprüfen:

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

Das bedeutet, beide leer sein müssen vor dem Beenden die ein Problem verursachen kann. Ich glaube, dass Sie verwenden möchten:

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

Answer 2

Wie Duncan darauf hingewiesen, ein Stapel möglicherweise nicht die beste Datenstruktur dafür. Ich nehme an, Sie wollen in Reihenfolge gehen, was bedeutet, dass Sie eine Warteschlange verwenden sollten.

Hier ist eine Implementierung. Ich habe bessere Namenskonventionen für Variablen verwendet, die nicht nur die Lesbarkeit, sondern auch das Debugging verbessern.

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 ... ... ... NEIN NEIN NEIN ... ... ... NEIN YES ...