1
\$\begingroup\$

Consider a coding system for alphabets to integers where 'a' is represented as 1, 'b' as 2, .. 'z' as 26. Given an array of digits (1 to 9) as input, write a function that prints all valid interpretations of input array.

Input: {1, 1} Output: ("aa", 'k") [2 interpretations: aa(1, 1), k(11)]

Input: {1, 2, 1} Output: ("aba", "au", "la") [3 interpretations: aba(1,2,1), au(1,21), la(12,1)]

Input: {9, 1, 8} Output: {"iah", "ir"} [2 interpretations: iah(9,1,8), ir(9,18)]

I'm looking for code-review, optimizations and best practices. I'm also verifying space complexity to be \$O(2^n)\$, where \$n\$ is the number of alphabets is the length of input array.

public final class FormulateAlphabets {

    private static final String[] data = {
        "", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n",
        "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"
    };

    private FormulateAlphabets() { }

    public static List<String> getAllStrings(int[] arr) {

        List<String> strList = new ArrayList<>();
        formulate(arr, 0,  false, strList, new StringBuffer());
        formulate(arr, 0,  true,  strList, new StringBuffer()); 

        return strList;
    }


    private static void formulate(int[] arr, int currPosition, boolean includeNextPosition, List<String> strlist, StringBuffer sb) {

        int nextPosition = 0;

        if (!includeNextPosition) {
            sb.append(data[arr[currPosition]]);
            nextPosition = currPosition + 1;
        } else {

            if ((currPosition + 1) == arr.length) return;

            int result = arr[currPosition] * 10 + arr[currPosition + 1];
            if (result <= 26) {
                sb.append(data[result]);
            } else {
                return;
            }

            nextPosition = currPosition + 2;
        }


        if (nextPosition == arr.length) {
            if (sb.length() > 0) {
                strlist.add(sb.toString());
                sb.deleteCharAt(sb.length()-1);
            }
            return;
        }

        formulate(arr, nextPosition, false, strlist, sb);
        formulate(arr, nextPosition, true, strlist, sb);

        if (sb.length() > 0) {
            sb.deleteCharAt(sb.length()-1);
        }
    }

}

public class FormulateAlphabetTests {

    @Test 
    public void test1() {
        int[] a1 = {1, 2, 3, 4};        
        assertEquals(Arrays.asList("abcd", "awd", "lcd"), FormulateAlphabets.getAllStrings(a1));
    }

    @Test 
    public void test2() {
        int[] a2 = {1, 2, 2, 1};  
        assertEquals(Arrays.asList("abba", "abu", "ava", "lba", "lu"), FormulateAlphabets.getAllStrings(a2));
    }

    @Test 
    public void test3() {
        int[] a3 = {1, 2, 3};
        assertEquals(Arrays.asList("abc", "aw", "lc"), FormulateAlphabets.getAllStrings(a3));
    }

    @Test 
    public void test4() {
        int[] a4 = {12, 23, 2};
        assertEquals(Arrays.asList("lwb"), FormulateAlphabets.getAllStrings(a4));
    }
}
\$\endgroup\$
  • \$\begingroup\$ "where n is the number of alphabets is the length of input array" - this makes no sense to me. \$\endgroup\$ – maaartinus Aug 21 '14 at 0:34
6
\$\begingroup\$

test4 makes no sense. The question states "Given an array of digits (1 to 9) as input...", yet your test input is {12, 23, 2}.


As the digits are 1-9, there's no way to represent 'j' (10) or 't' (20). I'm guessing that's a mistake in the question.


I'm also verifying space complexity to be \$O(2^n)\$

\$O(2^n)\$ is certainly an upper bound on the number of valid interpretations, but we can find a tighter bound.

Here's a hint: let's look at the number of interpretations of this sequence of inputs

{ }               1
{ 1 }             1
{ 1, 1 }          2
{ 1, 1, 1 }       3
{ 1, 1, 1, 1 }    5
...

Look familiar? I'm going to re-post part of an another answer of mine.

Suppose our array \$s = s_0 s_1 \ldots s_{n - 1}\$ is of length \$n\$. We define a function \$f\$ such that \$f(i)\$ is the number of ways to interpret the suffix of \$s\$ starting at position \$i\$: \$s_i s_{i + 1} \ldots s_{n - 1}\$. In this way, our final solution will be the value of \$f(0)\$.

How many ways are there to interpret the empty array? Just one, so we can write

\begin{align} f(n) &= 1. \end{align}

Now how about the suffix \$s_{n - 1}\$? Well if it's \$0\$, that's invalid; otherwise there's just one way to interpret it.

\begin{align} f(n - 1) &= \begin{cases} 0 &\mbox{if } s_{n - 1} = 0, \\ 1 & \mbox{otherwise}. \end{cases} \end{align}

Now for the general case, the suffix \$s_i s_{i + 1} \ldots s_{n - 1}\$.

If \$s_i = 0\$, there are no interpretations. Otherwise, we have two cases to deal with.

If \$10 \leq s_i s_{i + 1} \leq 26\$, we can interpret the suffix as

\begin{align} (s_i s_{i + 1}) \underbrace{s_{i + 2} \ldots s_{n - 1}}_{f(i + 2) \text{ interpretations}} \quad \mbox{ or } \quad (s_i) \underbrace{s_{i + 1} s_{i + 2} \ldots s_{n - 1}}_{f(i + 1) \text{ interpretations}}. \end{align}

Otherwise, we can only interpret the suffix as \begin{align} &(s_i) \underbrace{s_{i + 1} s_{i + 2} \ldots s_{n - 1}}_{f(i + 1) \text{ interpretations}}. \end{align}

Putting that all together, we get \begin{align} f(i) &= \begin{cases} 0 &\mbox{if } s_{i} = 0, \\ f(i + 1) + f(i + 2) & \mbox{if } s_i = 1 \mbox{ or } (s_i = 2 \mbox{ and } s_{i + 1} \leq 6), \\ f(i + 1) & \mbox{otherwise.} \end{cases} \end{align}

So in the worst case, for example { 1, 1, 1, ..., 1 }, this reduces to the \$n\$th Fibonacci number, giving us space complexity \$O(F_n)\$.

\$\endgroup\$
3
\$\begingroup\$
  • You have the empty character in data.

  • data is a poor name.

  • I'm not a fan of having an uninstantiable class with only a static method. The alphabet might change. So create a constructor that takes in an alphabet.

  • You shouldn't type the alphabet by hand. You can generate it programmatically.

  • Calling formulate always with true then with false looks odd. At the very least you should have a method that wraps that sequence of calls.

  • formulate is a poor name.

  • I'm not a fan of having the output of a method being stored in one of its input parameters.

  • You should rewrite your code for the more general problem where the "words" can be more than two digits long. It would actually simplify your code. You would at the very least get rid of the true/false business.

\$\endgroup\$
  • \$\begingroup\$ I don't understand what exacly you mean with true/false business in your last point... \$\endgroup\$ – Vogel612 Aug 21 '14 at 7:03
  • \$\begingroup\$ I meant formulate which must always be called with true then false. \$\endgroup\$ – toto2 Aug 21 '14 at 16:35
1
\$\begingroup\$

The idea of using recursion for this its fine. The implementation can be simplified.

In pseudo code:

String[] interprete(byte[] numbers) {
  return 
    (
      canInterpreteAsCharacter(numbers[0..1]
        ? toCharacter(numbers[0..1]) + interprete(numbers[2..]) 
        : []
    ) +
    toCharacter(numbers[0]) + interprete(numbers[1..])
}

(This pseudo code disregards type incompatibility between arrays, strings and characters.)

As you can see, the recursive function needs only a single input argument (the array of numbers) and a single output argument (the array/list of strings). Implementing it this way in Java will lead to a lot of array copies and thus ineffective code, but let's worry about that later.

public List<String> interprete (byte[] numbers) {
  List<String> result = new ArrayList<>();
  if (numbers.length == 0) {
    return result;
  }
  if (numbers.length == 1) {
    result.add("" + toCharacter(numbers[0]);
    return result;
  }
  byte merged = merge(numbers[0], numbers [1]);
  if (canInterprete(merged) {
    result.addAll(combine(toCharacter(merged), interprete(subarray(numbers, 2))));
  }
  result.addAll(combine(toCharacter(numbers[0]), interprete(subarray(numbers, 1))));
}

private byte merge(byte... bs) {
  byte result = 0;
  for (byte b : bs) {
    result = result * 10 + b;
  }
  return result;
}

private boolean canInterprete(byte b) {
  return b <= 'z' - 'a' + 1;
}

private char toCharacter (byte b) {
  return 'a' + b - 1;
}

private byte[] subarray (byte[] array, int offset) {
  byte[] result = new byte[array.length - offset];
  System.arrayCopy(array,0,result,offset,result.length);
  return result;
}

private List<String> combine (char first, List<String> rest) {
  List<String> result = new ArrayList<>();
  for (String s : rest) {
    result.add("" + first + s);
  }
  return result;
}

Now this code is easier to read, because it is written as a combination of smaller functions that have meaningful names, although some of the names can probably be improved.

My point is: get the logic right in your head first, write it down as pseudo-code for example and then code it along three same lines.

Now what about performance? The first problem is with the arrayCopy. To resolve it, we introduce the offset parameter to the recursive function, and use it to read the numbers from the array. The second problem is with the Lists that are created. This can also be resolved by passing additional parameters to the recursive function (although another way would be to store it in a field in the instance, which would mean you would create a new instance for each decode action.

public List<String> interprete(byte[] numbers){
  List<String> result = new ArrayList<>();
  interprete(numbers, 0, "", result);
  return result;
}
private void interprete(byte[] numbers, int offset, String part, List<String> result) {
  if (numbers.length == offset) {
    return;
  }
  if (numbers.length == offset + 1) {
    result.add(part + toCharacter(numbers[offset]);
    return;
  }
  byte merged = merge(numbers[offset], numbers [offset+1]);
  if (canInterprete(merged)) {
    interprete(numbers, offset+2, part + toCharacter(merged), result);
  }
  interprete(numbers, offset+1, part + toCharacter(numbers[offset]), result);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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