QuestionQuestion

Experimenting with ArrayList

In this assignment, you should right a method “isSubsequence” which takes two Arraylists as parameters and determines whether the first ArrayList is a subsequence of the second ArrayList. Your method must have the following signature:
public static <T> boolean subSequence(ArrayList<T> s1,ArrayList<T> s2)
What is a subsequence?

A sequence s1 is a subsequence of another sequence s2, if s1 can be derived from s2 by deleting some of its elements without changing the order of the remaining elements:
Here are some examples where s1 is a subsequence of s2:
- s1=<a,b,d> s2=<a,b,c,d,e,f>
- s1=<a,b,c,d,e> s2=<c,d,a,d,b,c,d,e>
- s1=<a,b,a,c>, s2=<a,b,a,c>
- s1=<a,b,c,a> s2=<b,c,d,a,e,c,a,e,a,f,b,b,e,c,d,e,a,b,d>
- s1=<> s2=<a,b,c>
- s1=<> s2=<>
Note that if s1 is empty, then regardless of s2, s1 is always a subsequence of s2.
Here are some examples where s1 is NOT a subsequence of s2:
- s1=<a,b,a,a> s2=<b,c,a,c,b,a>
- s1=<a,b,a> s2=<>
- s1=<a,b,a> s2=<b,c,a,c,b>
- s1=<a,b,c> s2=<b,c,a,c,b,a>
How do you determine whether s1 is a subsequence of s2?
Let’s take the following example:
s1=<b,d,f> s2=<a,b,c,d,e,f>
- first I check the first element in s1: “b” and I look for “b” in s2 and cross it out (I highlighted it in red):<a, b,c,d,e,f>
- Next, I check the next element in s1: “d” and I look at s2 after the point I last highlighted and look for “d” and cross it out (highlight it) : <a, b, c, d, e, f>
- Last, I check the next element in s1: “f” and I look at s2 after the point I last highlighted and look for “f” and cross it out (highlight it): : <a, b, c, d, e, f>
Now I stop. all the elements in s1 where found in s2 without breaking their order, so s1 is a subsequence of s2. If I get to the end of s2 while I have not still gone through all the elements in s1, so s1 is not a subsequent of s2.
Note: You only need to scan subsequence s2 once.

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

package dataStructures;

import java.util.ArrayList;
import java.util.Iterator;

public class SubSequenceTest<T>{

public static void main(String[] args)
{
ArrayList<Character> list1 = new ArrayList<Character>();
ArrayList<Character> list2 = new ArrayList<Character>();

list1.add('a');
list1.add('b');
list1.add('d');

list2.add('a');
list2.add('b');
list2.add('c');
list2.add('e');
list2.add('d');
list2.add('f');

System.out.println("List 1 is a sub-sequence of list2 = " + subSequence(list1, list2));
list1.clear();
list2.clear();

list1.add('a');
list1.add('b');
list1.add('c');
list1.add('d');
list1.add('e');

list2.add('c');
list2.add('d');
list2.add('a');
list2.add('d');
list2.add('b');
list2.add('c');
list2.add('d');
list2.add('e');

System.out.println("List 1 is a sub-sequence of list2 = " + subSequence(list1, list2));...
$30.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats