Padovan String Sequence Problem

Problem Find number of occurrences of input string in nth Padovan String P(n)
where P(0) = 'X', P(1)='Y' and P(2)='Z'
Input Parameters: needle string str to search for and number n
Conditions to handle:
if number n is >= 40 return -1
if string str has any other characters then X,Y and Z return -1

Solution

Solved this problem for preliminary round of one programming contest.

PadovanString.java

[code language="java"]
public class PadovanString {

public int stringOccurrences(int n, String str){
if (n >= 40)
return -1;
if (str.replaceAll("X|Y|Z", "").length() > 0)
return -1;
String res= pad(n);

/* print nth Padovan String
System.out.println(res);*/

/*replace search string with null and caculate number of occurences*/
return (res.length() - res.replaceAll(str, "").length())/(str.length());
}

public String pad(int n){

if (n == 0) return "X";
if (n == 1) return "Y";
if (n == 2) return "Z";
else return pad(n-2) + pad(n-3);

}
}
[/code]

Test.java

[code language="java"]
public class Test {
public static void main(String []args)
{
PadovanString p = new PadovanString();
System.out.println(p.stringOccurrences(20,"YZ"));
}
}
[/code]



Also, Length of Nth padovan string = Nth Padovan number