Betty the Cow has a hobby: car-watching. Every day she watches the cars go by on
ID: 3666219 • Letter: B
Question
Betty the Cow has a hobby: car-watching. Every day she watches the cars go by on the highway as she
eats in her pasture. However, just watching them gets boring, so she decided to make a game of it. At
the start of each day, she chooses a sequence of colors, e.g., (Red, Green, Red). She then spends the
rest of the day checking if her sequence shows up as a subsequence of the sequence of car colors that
go past her. (A subsequence shows up if the colors appear in order, but not necessarily contiguously.
For example, (Red, Green, Red) shows up in (Red, Green, Blue, Red) since each element appears in
the desired order, even though the Green and the second Red are separated by a Blue). If Betty sees
the subsequence she is looking for, she’s happy, if not she’s sad.
Farmer Mike wants a quick way of figuring out whether Betty is going to be happy or sad when she
comes in at the end of the day. Given the sequence of cars S that drove by and the subsequence P
that Betty was looking for that day, give him an algorithm to determine whether Betty will be happy
or not in O(|S|) time.
Explanation / Answer
We have two inputs to the algorithm
1) S: The sequence of colors that drove by the whole day
2) P: The subsequence of colors betty was looking to find
The idea is simple, we have two pointers, one at the beginning of P and the other at the beginning S. We move from the beginning to the end. At each cycle we compare the two colors the pointers are showing, and If they match we move both the pointers forward and if they don't match we only move the pointer in S forward.
The core of the algorithm would look like:
for(i=0,j=0;i<len(S)&&j<len(P);i++){
if(S[i]==P[j]) j++;
}
if(j==len(P)) then berry will be happy
else betty will be unhappy.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.