CODEWITHSUNDEEP
java
Emma Middleton
Emma Middleton

Reputation: 51

How to see if an array contains another?

Problem: Check to see if the array arr2 is contained within the arr1 in the same order. The arr2 could be contained anywhere with in arr1.

Examples:

contains({"1", "2", "3"}, {"1", "2"}) → true
contains({"1", "2", "3"}, {"2", "3"}) → true
contains({"1", "2", "3"}, {"2", "1"}) → false

My code works in all cases except when arr2 is shorter than arr1 and arr2 does not start on position 0 of arr1.

Here is my code:

public boolean contains(String[] arr1, String[] arr2){
if (arr2.length>arr1.length)
{
   return false;
}

int x=0;
if(arr2.length==arr1.length)
{
   for (int i=0; i<arr1.length; i++)
   {
      if(arr1[i]==arr2[i])
      {
         x++;
      }
   }
   if(x==arr1.length)
   {
      return true;
   }
   return false;
}

int y=0;

if(arr2.length<arr1.length)
{
   for(int i=0; i<arr2.length; i++)
   {
      if(arr1[i]==arr2[i])
      {
         y++;
      }
   }
}
if(y==arr2.length)
{
   return true;
}
  return false;
}

I would rather have hints instead of the answer itself. Thank you so much!

Upvotes: 2

Views: 212

Answers (4)

James Le
James Le

Reputation: 21

When reading your solution, i see there are 3 parts.

Part 1: if array 2 is smaller than array 1, then array 2 can not be a sub array of array 1

Part 2: compare each element of 2 array when they have the same size. Array 2 is sub array of Array 1 if all elements are the same

Part 3: compare each element of 2 array when array 2 size is smaller than array 1 size. There is an issue in part 2 and part 3. They have the same logic. Part 3 works fine if 2 array have the same size. In fact, if two arrays have the same size, part 2 would have taken care of this scenario. So step 2 and 3 are basically the same thing

I would revise part 3 as follow:

Part 3 (new): if array 2 is smaller than array 1, and array 2 is contained within array 1, then array 1 should have a sub array, in which each element of that sub array is equaled to each element in array 2

step 1: compare each element of array 2 to the sub array of array 1.

step 2: if all elements are equals, then array 2 is contained in array 1. if any of elements are not equal, repeat step 1 for the next sub array of array 1.

Note: if you are familiar with recursion, the solution will be neater. Every time we repeat step 1, we are solving the same problem as part of the general solution.

Below is the recursive solution. This solution does not take into account null and empty array.

<!DOCTYPE html>
<html>
<body>

<p>This example calls a function which performs a calculation, and returns the result:</p>

<p id="demo"></p>

<script>

function findSubArray(bigArray, smallArray, startIndexOfSubArray)
{   
    if((bigArray.length - startIndexOfSubArray) < smallArray.length)
        return false;
    for(index = 0; index < smallArray.length; index++)
    {
        if(bigArray[startIndexOfSubArray + index] != smallArray[index]){
            return findSubArray(bigArray,
                                smallArray,
                                startIndexOfSubArray = startIndexOfSubArray + 1);           
        }           
    }

    return true;

}

var bigArray = [1,3,3,4,5,6];
var smallArray = [4,5,7];

var isSubArray = findSubArray(bigArray, smallArray, 0);

document.getElementById("demo").innerHTML = isSubArray.toString();
</script>

</body>
</html>

Upvotes: 0

Jonas Heidelberg
Jonas Heidelberg

Reputation: 5024

You wanted hints only, so here is one:

In your if(arr2.length<arr1.length) statement, you are only looping to compare arr1[i] with arr2[i]. As you said yourself, this is only comparing whether arr2 matches the start of arr1.

To test for a case where arr2 starts at a later position, you would have to do a comparison between arr1[i+j] and arr2[i] for different j, i.e. you need another for loop here over possible "shifts" j between the array starting points, with your for i loop nested inside the for j loop. Make sure to reset your y to zero in the correct place.

Upvotes: 1

hiimjames
hiimjames

Reputation: 518

Here is your code modified to the right solution. You could do it better of course.

public boolean contains(String[] arr1, String[] arr2){
if (arr2.length>arr1.length)
{
   return false;
}

if(arr2.length==arr1.length)
{
   for (int i=0; i<arr1.length; i++)
   {
      if(!arr1[i].equals(arr2[i]))
      {
         retrun false;
      }
   }
return true;
}

int y =0; 

if(arr2.length<arr1.length)
{
   for(int i=0; i<=(arr1.length-arr2.length); i++)
   {
      for(int j=0; j<arr2.length;j++){
          if(arr1[i+j].equals(arr2[j])){
              y++;
          }
      }
       if(y == arr2.length){
           return true;
       }else {
         y = 0;
        }
   }
   return false;
}

Upvotes: 1

Ivan
Ivan

Reputation: 847

I would recommend looking at String#contains method implementation (specifically at String#indexOf static method). Algorithm looks very similar to your problem.

Upvotes: 0

Related Questions