Question

Develop an application that, given two sequences of words, will determine if the first is a subsequence of the second. The subsequence is defined as follow:

Given X = <x₁,x₂,…,x_n> a sequence of length n greater or equal to zero and Y = <y₁,y₂,…,y_m> a sequence of length m greater than or equal to zero, X will be consider a subsequence of Y if and only if there exists a strictly increasing sequence of elements K = <k₁, k₂,…,k_n> such that every element x_i is equal to y_j where j = k_i.

Consider the following examples:

• X = < a b a> and Y = <a b a> è X is a subsequence of Y
• X = < a b c> and Y = <a c b > è X is not a subsequence of Y
• X = < a b a> and Y = <b c a c b a> è X is a subsequence of Y
• X = < a b a> and Y = <b c a c a b> è X is not a subsequence of Y
• X = < a b a a> and Y = <b c a c b a> è X is not a subsequence of Y
• X = < a b a> and Y = <b c a c b> è X is not a subsequence of Y
• X = < a b c> and Y = <b c a c b a> è X is not a subsequence of Y
• X = < > and Y = <b c a c b a> è X is a subsequence of Y

Your Task:

1. The skeleton of the program is provided for you. You need to give implementation for method isSubsequence using appropriate Iterator objects. After the check is done the sequences must remain intact.
2. A sample run of the program and a UML diagram are provided.
3. Make sure that the output is correct (see Sample Run below).

public class Sequence
{
    private ArrayList<String>  sequence;

    public Sequence(String... input)
    {
        this.sequence = new ArrayList<>();
        Collections.addAll(this.sequence,input);
    }

    public Sequence (ArrayList<String> input)
    {
        this.sequence = new ArrayList<>(input);
    }

    public void add (String element)
    {
        this.sequence.add(element);
    }

    public void clear()
    {
        this.sequence.clear();
    }

    public String toString()
    {
        return this.sequence.toString();
    }


    /**
     * isSubSequenceOf - determine if one sequence is a subsequence of the other
     *
     * @param other the second sequence to test
     * @return    a true if the first list is a subsequence of the other
     */
    private boolean isSubSequenceOf(Sequence other)
    {
        // TODO Project 4
        boolean result = false;
        boolean foundMatch = false;
        Iterator<String> iterThis  = this.sequence.iterator();
        Iterator<String> iterOther  = other.sequence.iterator();
        String itemOfThisList = null;
        String itemOfOtherList = null;


        return result;
    }

Answer 1

• I have implemented the above problem as per the requirement in the question.
• I have attached the screenshot of output of the program.

Source code:-

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.Scanner;

public class Sequence
{
    private ArrayList<String> sequence;

    public Sequence(String... input)
    {
        this.sequence = new ArrayList<>();
        Collections.addAll(this.sequence,input);
    }

    public Sequence (ArrayList<String> input)
    {
        this.sequence = new ArrayList<>(input);
    }

    public void add (String element)
    {
        this.sequence.add(element);
    }

    public void clear()
    {
        this.sequence.clear();
    }

    public String toString()
    {
        return this.sequence.toString();
    }

    /**
     * isSubSequenceOf - determine if one sequence is a subsequence of the other
     *
     * @param other the second sequence to test
     * @return    a true if the first list is a subsequence of the other
     */
    private boolean isSubSequenceOf(Sequence other)
    {
        // TODO Project 4
        boolean result = false;
        boolean foundMatch = false;
        Iterator<String> iterThis = this.sequence.iterator(); // what is the iterator iterating over?
        Iterator<String> iterOther = other.sequence.iterator();
        String itemOfThisList, itemOfOtherList;

        if (this.sequence.isEmpty())
        {
            result = true;
        }
        else if (this.sequence.size() > other.sequence.size())
        {
            result = false;
        }
        else
        {
            while (iterThis.hasNext() && iterOther.hasNext())
            {
                itemOfThisList = iterThis.next();
                do
                {
                    itemOfOtherList = iterOther.next();
                    foundMatch = false;
                } while (iterOther.hasNext() && !itemOfThisList.equals(itemOfOtherList));
                if (itemOfThisList.equals(itemOfOtherList))
                    foundMatch = true;
            }
            if (foundMatch && !iterThis.hasNext())
            {
                result = true;
            }
        }
        return result;
    }

  
    public static void main(String args[])
    {
        Scanner keyboard = new Scanner(System.in);
        Sequence seq1 = new Sequence("a","b","c");
        System.out.println("The seq1 is " + seq1);

        System.out.println("==> Please enter a sequence of words on a single line,"
                + " (words should be separated by spaces), or stop.");
        String line = keyboard.nextLine();
        while (!line.equalsIgnoreCase("stop"))
        {
            Sequence seq2 = new Sequence(line.split("\\s"));
            System.out.println("Is " + seq1 + " a subsequence of " + seq2 + ": " + seq1.isSubSequenceOf(seq2));
            System.out.println("==> Please enter a sequence of words on a single line,"
                    + " (words should be separated by spaces), or stop.");
            line = keyboard.nextLine();
        }

      
    }
}

--------------------------------------------------------------------------------------------------------------------------------

Output:-

***********************************************************************************

if you are satisfy with my answer then please,please like it.