Hi!
The first input parameter will be a list with numbers, the second will also be a list with numbers. The essence of the problem is to find out whether the second list is a subsequence of the first.
To do this, we will need a pointer that will point to items from the second list. Let’s start moving on each element from the first list and check whether it is equal to the element from the second list indicated by the pointer.
For example, the first list 5, 3, 22, 25, 9, -5, 8, 7 and the second 3, 9, -5, 7. The pointer points to 3
>3, 9, -5, 7
We begin to sort the numbers from the first list and compare them with the pointer. 3 is not equal to 5 and therefore we pass to the following element. 3 = 3 means we move the pointer to one to the right
3,> 9, -5, 7
Compare with the next item in the first list 22! = 9 25! = 9 9 = 9 match again, and move the pointer to the right again
3, 9,> -5, 7
Next, sort the elements of the first list -5 = -5 again move the pointer to the right and move on the first list 8! = 7 7 = 7
Thus we found the last element from the second list and therefore it is a subsequence of the first.
An example of a solution on go
package main
import "fmt"
func main() {
sequence := []int{5, 3, 22, 25, 9, -5, 8, 7}
subsequence := []int{3, 9, -5, 7}
fmt.Println(validateSubsequence(sequence, subsequence))
}
func validateSubsequence(sequence []int, subsequence []int) bool {
subsequencePtr := 0
for _, num := range sequence {
if num == subsequence[subsequencePtr] {
subsequencePtr++
}
}
return subsequencePtr == len(subsequence)
}