1
\$\begingroup\$

Write a static method named contains that accepts two arrays of integers a1 and a2 as parameters and that returns a boolean value indicating whether or not a2's sequence of elements appears in a1 (true for yes, false for no). The sequence of elements in a2 may appear anywhere in a1 but must appear consecutively and in the same order. For example, if variables called list1 and list2 store the following values:

int[] list1 = {1, 6, 2, 1, 4, 1, 2, 1, 8}; int[] list2 = {1, 2, 1};

Then the call of contains(list1, list2) should return true because list2's sequence of values {1, 2, 1} is contained in list1 starting at index 5. If list2 had stored the values {2, 1, 2}, the call of contains(list1, list2) would return false because list1 does not contain that sequence of values. Any two lists with identical elements are considered to contain each other, so a call such as contains(list1, list1) should return true.

You may assume that both arrays passed to your method will have lengths of at least 1. You may not use any Strings to help you solve this problem, nor methods that produce Strings such as Arrays.toString.

I'm looking for general feedback to improve my future code. I'm intent on learning Java, so any style tips would be well appreciated. Other ways to accomplish this task?

public static boolean contains(int[] list1, int[] list2) {
    for (int i = 0; i <= (list1.length - list2.length); i++) {
        if (list1[i] == list2[0]) {
            for (int j = 1; j < list2.length; j++) {
                if (list1[i + j] == list2[j]) {
                    if (j == (list2.length - 1)) {
                        return true;
                    }
                } else {
                    break;
                }
            }
        }
    }
    return false;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ What if list1.length < list2.length ? \$\endgroup\$ – aGer Nov 13 '17 at 15:42
  • 1
    \$\begingroup\$ then the for loop won't be executed, since i = 0 will never be less than (list1.length - list2.length), meaning that this code will correctly return false. The question also states to test "whether or not a2's sequence of elements appears in a1 (true for yes, false for no). " \$\endgroup\$ – cody.codes Nov 13 '17 at 16:07
2
\$\begingroup\$
        if (list1[i] == list2[0]) {
            for (int j = 1; j < list2.length; j++) {
                if (list1[i + j] == list2[j]) {

We can drop this from three lines to one.

        for (int j = 0; j < list2.length && list1[i + j] == list2[j]; j++) {

A side benefit is that this handles the case where list2 is empty (zero length). The original code would crash in that case.

At the expense of an extra comparison (which could be compiled out), we get rid of two levels of indent and

                } else {
                    break;

Because this will leave the loop automatically. It won't be necessary to break out manually.

It might be better to replace

        if (list1[i] == list2[0]) {
            for (int j = 1; j < list2.length; j++) {
                if (list1[i + j] == list2[j]) {
                    if (j == (list2.length - 1)) {
                        return true;
                    }
                } else {
                    break;
                }
            }
        }

with

        int j = 0;
        while (j < list2.length && list1[i + j] == list2[j]) {
            j++;
        }

        if (j == list2.length) {
            return true;
        }

Moving the scope of j outside the inner loop allows us to move the test out of the loop as well. So rather than testing on every iteration, we can test just once.

Alternately

        for (int j = 0; list1[i + j] == list2[j]; j++) {
            if (j + 1 >= list2.length) {
                return true;
            }
        }

Does the same thing as the original code. It may not be obvious, but this does the same thing with fewer comparisons.

But we're back to throwing an exception if list2 is zero length. This does exactly the same thing as the original code with fewer comparisons and less code.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.