Job Interview Question Numbers are assigned to each letter of the alphabet, where a=1, b=2, ..., z=26. A word can then be encoded based on those numbers, so for example "apple" is encoded as "11616125". However, "11616125" can also be decoded to many other strings, such as "kfafay" (11 6 1 6 1 25) and "aafple" (1 1 6 16 12 5). Letters are never …

gistfile1.java

import java.util.ArrayList;

public class DecoderTree {

  public static void main(String args[]) {
		System.out.println(decode("2222"));
		System.out.println(decode("105"));
		System.out.println(decode("2175"));
		System.out.println(decode("0000"));
	}

	public static ArrayList<String> decode(String s) {
		ArrayList<String> temp = new ArrayList<String>();
		if (s.equals(""))
			return temp;
		if (s.charAt(0) == '0')
			return null;

		String left = s.substring(0, 1);
		ArrayList<String> lhs = decode(s.substring(1));
		if (lhs != null) {
			if (lhs.size() == 0) {
				temp.add(Character.toString((char) (Integer.parseInt(left) + 96)));
			} else {
				for (String x : lhs)
					temp.add(Character.toString((char) (Integer.parseInt(left) + 96))
							+ x);
			}
		}

		if (s.length() > 1) {
			String right = s.substring(0, 2);
			if ((Integer.parseInt(right) <= 26)) {
				ArrayList<String> rhs = decode(s.substring(2));
				if (rhs != null) {
					if (rhs.size() == 0) {
						temp.add(Character.toString((char) (Integer
								.parseInt(right) + 96)));
					} else {
						for (String y : rhs)
							temp.add(Character.toString((char) (Integer
									.parseInt(right) + 96)) + y);
					}
				}
			}
		}
		return temp;
	}
}