import java.io.*;
import java.util.*;

class Solution {
  public static void main(String[] args) {
    System.out.println("Running");

    Map<String, String> alphabet = new HashMap<String, String>();
    alphabet.put("1", "a");
    alphabet.put("2", "b");
    alphabet.put("3", "c");
    alphabet.put("4", "d");
    alphabet.put("5", "e");
    alphabet.put("6", "f");
    alphabet.put("7", "g");
    alphabet.put("8", "h");
    alphabet.put("9", "i");
    alphabet.put("10", "j");
    alphabet.put("11", "k");
    alphabet.put("12", "l");
    alphabet.put("13", "m");
    alphabet.put("14", "n");
    alphabet.put("15", "o");
    alphabet.put("16", "p");
    alphabet.put("17", "q");
    alphabet.put("18", "r");
    alphabet.put("19", "s");
    alphabet.put("20", "t");
    alphabet.put("21", "u");
    alphabet.put("22", "v");
    alphabet.put("23", "w");
    alphabet.put("24", "x");
    alphabet.put("25", "y");
    alphabet.put("26", "z");

    List<String> possibleStrings = getAllPossibleStrings(alphabet, "12345");
    System.out.println("Possibilties");
    if (possibleStrings == null) {
      System.out.println("No valid strings which use the whole input");
    } else {
      for (String str : possibleStrings) {
        System.out.println(" " + str);
      }
    }
  }

  // Returns the list of all strings that could be made from input, encoded into the "alphabet" map.
  // If there are no valid strings return null. Assumes "input" always starts with a value and that alphabet is initialized.
  // If we can't assume that, I'd add a wrapper method which handles sanitation.
  public static List<String> getAllPossibleStrings(Map<String, String> alphabet, String input) {
    List<String> result = new ArrayList<String>();

    // Base case, we're at the end of the string.
    if (input.length() == 0) {
      result.add("");
      return result;
    }

    for (int i = 0; i < input.length(); i++) {
      // Test each successive substring. If we cannot assume anything about the keys, then go until we're done.
      // If we do know the range we can fast-fail and only check the number of digits in the dictionary possibilities.
      String testKey = input.substring(0, i+1);

      if (alphabet.containsKey(testKey)) {
        List<String> subProblemSolution = getAllPossibleStrings(alphabet, input.substring(i+1));

        // Sub-string isn't empty, but also has no valid options. In this case, the current substring
        // is invalid, so check the next one.
        if (subProblemSolution == null) {
          continue;
        }

        String testValue = alphabet.get(testKey);

        for (String soln : subProblemSolution) {
          String newString = testValue + soln;
          result.add(newString);
        }
      }
    }

    if (result.size() == 0) {
      return null;
    }
    return result;
  }
}