import java.util.*;

public class MyClass {


    public static int count(String str, List<String> letters, Map<String, Integer> vocab) {
        System.out.println(str);
        if (str.isEmpty()) { // base case - a combination was found
            return 1;
        }
        if (vocab.containsKey(str)) { // result was already computed and present in the map
            System.out.println("trovato valore per " + str + ": " + vocab.get(str));
            return vocab.get(str);
        }

        int count = 0;

        for (String letter: letters) {
            System.out.println(str + "," + letter);
            if (str.startsWith(letter)) {
                count += count(str.substring(letter.length()), letters, vocab);
            }
        }
        vocab.put(str, count); // storing the total `count` into the map
        System.out.println(count);
        return count;
    }

    public static void main(String[] args) {

        List<String> letters = List.of("0", "00", "001", "010", "0010", "0100", "0110", "0001"); // binary letters

        System.out.println(count("000100100010010000100100001001100", letters, new HashMap<>())); // DP
        //System.out.println(count("00100", letters));                  // brute-force recursion
    }
}