1
\$\begingroup\$

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;
    }

}
\$\endgroup\$
0

2 Answers 2

4
\$\begingroup\$

Useless code

Currently, your code has some useless parts to it:

  1. You have a set, but you never add anything to it. When you reach the end of the string, you check your set for it containing something, but it never does. You can just remove that whole set and do count++ when you reach the end of the string. The way you are parsing the input, there is no way you can ever reach the same output string more than once.

  2. Your solve() function always returns 0. And nobody even checks the return value. So you should make your solve() function return void.

Incorrect answer

Currently, your program will return an incorrect answer if count ever increases past \$2^{31}\$. The question warned about this, so you should make count be long instead.

Too slow

The problem with your program is that you are just computing the answer in the brute force way, by generating every possible output. This problem requires a dynamic programming technique to solve faster. In simple terms, you are solving the same subproblem repeatedly. If you just remembered the answer for each subproblem you already solved, then things would run much faster.

Here is an example of how I would fix your program to run faster:

import java.util.Scanner;

public class AlphaCode {    
    static int n;
    static long [] solved;

    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();
            solved = new long[n];
            for (int i=0; i<n; i++) {
                solved[i] = -1;
            }
            long ret = solve(s, 0);
            System.out.println(ret);
        }
    }

    private static long solve(String s, int i)
    {
        long count = 0;

        if (i >= n) {
            return 1;
        }

        if (solved[i] != -1) {
            return solved[i];
        }

        for (int j = 0; j < 2 && i + j < n; ++j) {
            int x = Integer.parseInt(s.substring(i, i + j + 1));
            if (x <= 26) {
                count += solve(s, i + j + 1);
            }
        }
        solved[i] = count;
        return count;
    }

}
\$\endgroup\$
2
\$\begingroup\$

Apart from what @JS1 said, advice I would like to give is that using System.out.println() frequently is very costly so instead of that either use PrintWriter or print the entire output at once using StringBuilder. The reason is that the latter two are buffered and will improve the performance.

You need to stop using Scanner and start using BufferedReader for the same cause as stated above.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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