A recursive method to check pattern in an array

Question

I'm trying to write a recursive method in Java that will take two arrays of int and return true/false if the first array represent a pattern of the second array, in that way - (the pattern array accept 0, 1 or 2. 0 represent one or two digits number, 1 represent one digit numbers and 2 represent two digits numbers. so if I send {2, 3, 57} and {1, 0, 2} it will return true. if i put {2, 555, 57} and {1, 0, 2} it will return false. also, if i put {2,3,573**,4,34,35}** and {1, 0, 2} i still need to get true, since part of the array represnt the pattern.

i came up with this:

private static boolean match(int [] a, int [] pattern, int i, int j, int c, int subArr)
{
    if(a.length < pattern.length)
        return false;
    else if(pattern.length == 0)
        return true;
    else if(pattern.length == a.length && check(a, pattern, i, j))
        return true;
    else if(check(a, pattern, i++, j++))
    {
        return check(a, pattern, i, j);
    }

    else return false;    
}


private static boolean check(int [] a, int [] pattern, int i, int j)
{        
    if(pattern[j] == 1 && (checkDigits(a[i]) == 1))
    {
        return true;
    }            
    else if(pattern[j] == 2 && checkDigits(a[i]) == 2)
    {
        return true;
    }
    else if(pattern[j] == 0 &&(checkDigits(a[i]) == 1 || checkDigits(a[i]) == 2 )){
        return true;
    }
    else return false;

}


private static int checkDigits(int k){
       int length = (int)(Math.log10(k)+1);
       return length;

    }

the match method is doing all the checks. the check methode is checking the pattern and checkDigits the number of digits. My problem is with 3 digits numbers. if i put for exemple { 2, 123, 54 } and {1, 0, 2} I get true and not false. I belive the problem is in the check method but I can't locate the problem.

Answer 1

I am a little unclear with your code. But it can be done in a simpler way using a for loop.

The basic algorithm you need to follow would be:

j=0
for(i = 0 to a.length){
if number of digits(a[i]) == pattern[j] {
j++
}
}
 if j == pattern.length
print its a match
else
it is not.

This small piece of code will work for every case.

Instead of the for loop, just call it every time.

Answer 2

A truly recursive solution might be the following:

import java.util.Arrays;

public class Checker {
//0 represent one or two digits number, 
//1 represent one digit numbers and 
//2 represent two digits numbers
public boolean match(int [] a, int [] pattern, int i, int j)
{
    if(pattern.length == 0) return true;
    if(pattern.length == a.length) {
         return check(a, pattern);
    } else {
        return false;
    }
}

    //recursive function
private  boolean check(int [] a, int [] pattern) {
    boolean firstDigitCheck = false;
    switch (pattern[0]) {
        case 0: firstDigitCheck = checkDigits(a[0]) <3;break; // 1 or 2
        case 1: firstDigitCheck = checkDigits(a[0]) <2;break; // 1
        case 2: firstDigitCheck = checkDigits(a[0]) ==2;break// 2
        default:break;//not important (we trust the pattern format)
    }       
    if (a.length==1) {//base step (array of dimension 1) 
        return firstDigitCheck;
    } else {//recursive step on the left-truncated arrays
        return firstDigitCheck && check(Arrays.copyOfRange(a, 1, a.length), Arrays.copyOfRange(pattern, 1, pattern.length));
    }
}


public int checkDigits(int k){
       int length = (int)(Math.log10(k)+1);
       return length;
}
}

Answer 3

Check this code I wrote right now, I added comments to the code, and if you run it. I wrote some text on the console to explain to you how it's working. So at the end when you want to use it, just remove the system.out.print

public class ArrayPattern {
    static int numbers[] = {1,10,20,3,30};
    static int pattern[] = {0,0,2,2};

    public static void main(String[] args) {
        System.out.println(isPattern(0, 0));
    }

    /**
     * Recursive method that checks for the pattern. If it fails to match pattern starting from index i, it 
     * tries starting from index i+1
     * */
    public static boolean isPattern(int index, int consec){

        // If all pattern values where matched consecutively
        if(consec == pattern.length)
            return true;

        // If the numbers ended and the pattern wasn't found
        if(index == numbers.length)
            return false;

        // If the current number matches the pattern, check the next number at index + 1
        if(checkPattern(pattern[consec], numbers[index])){
            System.out.println(pattern[consec] +" => "+ numbers[index]);
            return isPattern(index+1, consec+1);
        }

        // If the pattern was not found, starting from a specific index. Start from the next index to check if the pattern can be found
        System.out.println(String.format("\nFailed to match pattern, try starting from index: %d\n", (index - consec + 1)));
        return isPattern(index - consec + 1, 0);
    }

     /**
 * Just chesk the pattern:
 * 0 => 1 or 2 digits. 
 * 1 => 1 digit. 
 * 2 => 2 digits 
 */
    public static boolean checkPattern(int pattern, int value){
        String sValue = String.format("%d", value);
        switch (pattern) {
            case 0:
                return sValue.length() <= 2;
            default:
                return sValue.length() == pattern;
        }
    }
}

Answer 4

If I understand your question, then the element in array, "a", at index 'j' can have a certain number of digits based on the number at the element at index 'j' in pattern.

You could accomplish this with a for loop;

boolean result = true;
int [...] a = ...
int [...] pattern = ...
for (int j = 0; j < a.length(); j++) {
    if (result) {
        if (pattern[j] = 0) {
            if (a[j].toString().length() > 2) {
                result = false;
            }
        } else if (pattern[j] = 1) {
            if (a[j].toString().length() != 1) {
                result = false;
            }
        } else if (pattern[j] = 2) {
            if (a[j].toString().length() != 2) {
                result = false;
            }
        }
    }
}

That should get the job done, or something similar.