-1

I am trying to write a recursive function to check whether one array is contained in a second array (my example is also sub-array) and returns true or false.

For example: [d, e] is contained in [a, b​​, c, d, e, f]

.

I know how to check without recursion (using for loops), but can not think of a solution using recursion.

Andy Hayden
  • 359,921
  • 101
  • 625
  • 535
Dana Yeger
  • 617
  • 3
  • 9
  • 26

2 Answers2

1

The principle is the following:

0) If the first array is longer than the second one, it's not a subarray.

1) If the second array begins with the first (like [a,b] and [a,b,c,d]), then it's a subarray.

2) Else: If the first array is a subarray of the tail of the second one (that means, the part after the first element), then it's a subarray.

Just to be sure: tail([a,b,c,d]) == [b,c,d] (since I don't know how that's called in Java.)

phipsgabler
  • 20,535
  • 4
  • 40
  • 60
  • I assumed the OP was looking for a _subarray_, not a _subset_ - so actually the first one being an infix of the second one. That really isn't clear exactly from the quaestion, though he mentioned _subarray_ explicitly in the description - that's why I chose this algo. I'll try to clarify this. – phipsgabler Jun 05 '12 at 09:14
0

You can use hashing to store elements of large array in hash table and then check whether each element of sub array is there in hash table or not, If all elements found then it will be subarray.

user1362740
  • 24
  • 1
  • A sub-array has a very exacting definition. [b c] is a sub-array of [a b c d], but [c b] is *not*. It is important that the elements be such that the sub array is a 'part' of the array. – ArjunShankar Jun 05 '12 at 09:14