文字列のサブシーケンスのクエリ

Question

文字列SおよびQクエリが与えられた場合、各クエリには文字列Tが含まれます。TがSのサブシーケンスであれば "Yes"、それ以外の場合は "No"を出力します。 私はアルゴリズムを学び、それらを実装しようとしています。 私はJavaで以下のコードを書かれている：私はこれとEclipseでのデバッグしようとした

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

、それがあれば状態に入ることはありません。誰かが私が間違っているところを説明してください。

Answer 1

StackはLIFOデータ構造です。あなたが取得している

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

最後の2つの文字が追加さ：

これは、あなたが実行したときを意味します。この場合、sとg。

これは、ifステートメントが満たされないことを意味します。 2回目に、Stack.peekを使用しているのでソフトウェアがループしていますが、要素は変更されていません。したがって、あなたのwhileループは、sとgを何度も繰り返しています。それらは決して等しくないので、あなたのifは決して満たされないので、あなたのwhileループは無限になります。

はまた、あなたがチェックしている：

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

これが問題を引き起こす可能性が終了する前に空になるように、両方の必要性を意味します。私はあなたが使いたいと思う：

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

Answer 2

ダンカンは指摘しているように、スタックはこのための最良のデータ構造ではないかもしれません。私はあなたが順番に行きたいと思っています。つまり、キューを使うべきです。

ここに実装があります。私は可読性だけでなく、デバッグにも役立つより良い変数命名規則を使用しました。

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