Given two arrays of numbers, how to check if the first sequence is a sub sequence of second sequence.
For example [3, 7, 11] is a sub-sequence of [9, 3, 1, 7, 5, 11]
where as [4, 8, 9] is not a sub-sequence of [6, 4, 9, 2, 8]
The algorithm here is simple.
For example [3, 7, 11] is a sub-sequence of [9, 3, 1, 7, 5, 11]
where as [4, 8, 9] is not a sub-sequence of [6, 4, 9, 2, 8]
The algorithm here is simple.
- Let us assume two indices i, j point to the beginning of sub-sequence and sequence respectively.
- Do the following until we reach the end of any sequence.
- If both the elements are same, increment both indices.
- Otherwise increment j only.
At the end of this iteration, if we have seen all the elements of sub-sequence in the given sequence, we are done! otherwise we have not found!
Here is the code in C++ which implements the above approach. This runs in O(n) time and O(1) space. For Python code click here. For Java code click here.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*; | |
import java.lang.*; | |
import java.io.*; | |
/* Name of the class has to be "Main" only if the class is public. */ | |
class Codechef | |
{ | |
public static void main (String[] args) throws java.lang.Exception | |
{ | |
Scanner reader = new Scanner(System.in); | |
int t = reader.nextInt(); | |
while( t-- > 0 ) | |
{ | |
int n = reader.nextInt(); | |
int i; | |
int [] seq = new int[n]; | |
for( i = 0; i < n; i++ ) | |
seq[i] = reader.nextInt(); | |
int m = reader.nextInt(); | |
int [] subSeq = new int[m]; | |
for( i = 0; i < m; i++ ) | |
subSeq[i] = reader.nextInt(); | |
if( isSubSequence(subSeq,seq) ) | |
{ | |
System.out.println("Yes"); | |
} | |
else | |
{ | |
System.out.println("No"); | |
} | |
} | |
} | |
public static boolean isSubSequence(int []subSeq, int []seq) | |
{ | |
int i,j; | |
for( i = 0, j = 0; i < subSeq.length && j < seq.length; ) | |
{ | |
if (subSeq[i] == seq[j]) | |
i++; | |
j++; | |
} | |
return i == subSeq.length? true:false; | |
} | |
} |