I'm trying to solve Alphacode on SPOJ. The challenge is to count the ways to split a string of up to 5000 digits into a sequence of numbers, each ranging from 1 to 26.
It works fine for small numbers but exceeds the time limit for bigger numbers. I'm using the exhaustive recursive traversing.
Is there a way to make it optimal?
import java.util.HashSet;
import java.util.Scanner;
public class AlphaCode {
static int n;
static HashSet<String> set;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String s = sc.nextLine();
if (s.equals("0")) {
break;
}
n = s.length();
char[] c = new char[n];
set = new HashSet<String>();
count = 0;
solve(s, 0, c);
System.out.println(count);
}
}
static int count = 0;
private static int solve(String s, int i, char[] st) {
if (n == i) {
// System.out.println(st);
if (set.contains(st.toString())) {
return 0;
}
count++;
return 0;
}
for (int j = 0; j < 2 && i + j < n; ++j) {
int x = Integer.parseInt(s.substring(i, i + j + 1) + "");
if (x <= 26) {
// System.out.println(i + " " + j + " " + s.substring(i, i + j +
// 1));
st[i] = (char) (x + 'A' - 1);
solve(s, i + j + 1, st);
}
}
return 0;
}
}