Check if Character-array contains all elements in a smaller Character-array in Java

Question

I am trying to compare two character arrays, where the first array is ONE character longer than the second array. I want to see if the bigger array contains all the characters in the smaller array.

For instance, given arrays:

char[] biggest = {'a', 'b', 'c', 'd', 'e'};  //5 elements
char[] smallest = {'c', 'b', 'd', 'a'};  //4 elements

Comparing these should evaluate to true, because the smaller array contains characters c, b, d, and a, all which are included in the biggest array (regardless of the order).

Now, here is what I am thinking:

• Start with a for-loop that iterates through the biggest array, one character at a time
• See if the current character can be found in the smallest array
• If there is a match, increment a matchCounter.
• Do so until reaching the end of the biggest array
• If the matchCounter is equal to the smallestArray.length, return true.

Following is the code I have:

int matchCounter = 0;
//For each character in the biggest array
for(int i = 0; i < biggest.length; i++) {
    //Loop through the smallest array
    for(int j = 0; j < smallest.length; j++) {
        if(biggest[i] == smallest[j]) {  //See if the current character in the biggest array exists anywhere in the smallest array
            matchCounter++;
        }
    }
}

Any help is highly appreciated!

** UPDATE **

After running this, I don't get the expected answer. I think the problem arises when I have arrays containing duplicate characters:

For instance

char[] biggest = {'s', 'e', 'e', 'i', 'n', 'g'};
char[] smallest = {'e', 'e', 'i', 'g', 'n'};

    /*Loop to compare biggest and smallest, incrementing matchCounter when equal. */

    //If the biggest array has a matchCount equal to the smallest array (means the biggest array contains all the characters in the smallest array, plus an additional character)
    if(matchCounter == word.length()) {
        System.out.println("Suggested word: " + foundWord);
    }

Because it seems to be working fine otherwise!

Answer 1

Your approach will give the correct answer, but it's quite slow, since you are guaranteed to loop all the way through each array each time, giving O(n²) runtime.

One way to make this much faster, while maintaining a similar approach would be to sort the bigger set. This allows you to do a binary search for each character in the smaller set, rather than having to iterate all the way through each time:

    int matchCounter = 0;
    Arrays.sort(biggest);
    for (char c : smallest) {
        if (Arrays.binarySearch(biggest, c) >= 0) {
            matchCounter++;
        }
    }
    System.out.println(matchCounter); // 4