3
\$\begingroup\$

I was wondering, beyond the standard improvements that this needs, is there a more "clever" way of solving this problem?

The problem is to translate letters into digits without changing the format of the original string. The conversion is based on the international standard letter/number mapping on phones (i.e. where ABC is 2, DEF is 3, ..., PQRS is 7, TUV is 8, and WXYZ is 9).

public class Keypad {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        System.out.print("Enter a string: ");
        String s = input.nextLine();

        System.out.println(getNumbers(s));
    }

    public static String getNumbers(String s) {
        String result = new String();

        //Read and append s onto result
        for (int i = 0; i < s.length(); i++) {
            if (Character.isLetter(s.charAt(i))) {
            result += getNumber(Character.toUpperCase(s.charAt(i)));
            }
            else {
                result += s.charAt(i);
            }
        }
        return result;
    }

    public static int getNumber(char upperCaseLetter) {
        int number = ((upperCaseLetter - 'A') / 3) + 2;
        if (number < 7) {
            return number;
        }
        else if (upperCaseLetter - 'A' < 20) {
            return 7;
        }
        else if (upperCaseLetter - 'A' < 23) {
            return 8;
        }
        else {
            return 9;
        }
    }
}
\$\endgroup\$
4
\$\begingroup\$

A much simpler solution would be to use a lookup table. A mapping implemented using a lookup table would be easier to understand, with no magic numbers.

Furthermore, phone numbers are more numeric strings than numbers, so I'd make it a char-to-char lookup.

Repeated string concatenation is bad for performance. To compose a string, use a StringBuilder.

public class Keypad {
    private static final char[] DIGITS = (
                 // ABC     DEF
                   "222" + "333" +
        // GHI      JKL     MNO
          "444"  + "555" + "666" +
        // PQRS     TUV     WXYZ
          "7777" + "888" + "9999").toCharArray();

    public static String getNumbers(CharSequence s) {
        StringBuilder result = new StringBuilder(s.length());
        for (int i = 0; i < s.length(); i++) {
            char c = Character.toUpperCase(s.charAt(i));
            if ('A' <= c && c <= 'Z') {
                result.append(DIGITS[c - 'A']);
            }
        }
        return result.toString();
    }
}
\$\endgroup\$
2
\$\begingroup\$

There are two issues with your code which should be addressed. The first is the heavy cost of all the conditions you are performing each time you run. @200_success solves most of that problem by using a lookup table. It saves a lot of runtime code by replacing it with pre-computed code.

The second issue is the handling of unexpected characters. You use the Character.isLetter(...) call to determine if the character is a letter, but this call is defined to include unicode characters "OTHER_LETTER" and also "MODIFIER_LETTER". These will all be translated as the value 9 in your code.

There is a mathematical way to compute the results you want, with one exception. The trick is to identify that there are three keys-per-number for all keys, except key 7, and then there is an exception case with input Z, which is an overflow. If we calculate a 'value' and an 'offset' for each letter, and then do an integer truncation on it, we can convert it directly to a specific number. The trick is to find the constants that are needed. I did the calculation as:

// we want mostly 3 letters per key..... except PQRS
// so, set the span for each letter to 1/3 of the full span, less a small
// amount so that there can actually be 4 in some keys. 
private static final double SPAN = (1.0 / 3.0) - (1.0 / 260.0);
// and we want those 4 letters to happen on key 7 - 15 letters in.
private static final double OFFSET = 7.0 - (SPAN * 15);

Now, with those constants programmed in, for any valid key, we can do the computation:

    final int comp = Character.toUpperCase(letter) - 'A';
    char key = (char)('0' + OFFSET + comp * SPAN);

This will convert valid input characters to the characters 2 through 9 (except for the valid input characters z and Z which it converts to [

So, we end up with the following function:

public static final char charForKey(final char letter) {
    final int comp = Character.toUpperCase(letter) - 'A';
    if (comp < 0 || comp >= 26) {
        return letter;
    }
    char key = (char)('0' + OFFSET + comp * SPAN);
    // correct Z overflow to 10.
    return key > '9' ? '9' : key;
}

Now, using Java 8 lambda expressions, you can make it pretty, with:

public static final String keysFromNumber(String input) {
    StringBuilder sb = new StringBuilder(input.length());
    input.chars().forEach(c -> sb.append(charForKey((char)c)));
    return sb.toString();
}

I have some test cases, and other interesting tidbits in this ideone.

I suspect the computation will be faster than the lookup table, and certainly faster than your solution. Performance is not always the target, but I am putting together a performance testcase anyway.

here's the performance numbers, with an interesting lesson:

Task KeyPads -> FabZeros: (Unit: MICROSECONDS)
  Count    :    200000      Average  :    7.4930
  Fastest  :    5.5050      Slowest  : 6395.8520
  95Pctile :    9.3840      99Pctile :   17.4220
  TimeBlock : 10.901 7.486 7.544 7.319 8.504 6.129 6.515 7.761 6.690 6.083
  Histogram : 195075  3270   908    73    11   649     3     0     0    10     1

Task KeyPads -> 200_success: (Unit: MICROSECONDS)
  Count    :   200000      Average  :   0.8320
  Fastest  :   0.6910      Slowest  : 905.2690
  95Pctile :   1.1750      99Pctile :   2.3050
  TimeBlock : 1.416 0.810 0.804 0.742 0.804 0.736 0.769 0.737 0.771 0.740
  Histogram : 195483  3148   661   398   228    66    13     0     1     1     1

Task KeyPads -> rolfl: (Unit: MICROSECONDS)
  Count    :    200000      Average  :    1.8090
  Fastest  :    1.5450      Slowest  : 3161.7340
  95Pctile :    2.5750      99Pctile :    4.5570
  TimeBlock : 2.856 1.767 1.767 1.640 1.763 1.640 1.697 1.636 1.698 1.632
  Histogram : 196950  1305  1122   452   146    17     3     4     0     0     1

Task KeyPads -> rolflNS: (Unit: MICROSECONDS)
  Count    :    200000      Average  :    0.9380
  Fastest  :    0.7700      Slowest  : 3443.5900
  95Pctile :    1.3090      99Pctile :    2.5260
  TimeBlock : 1.506 1.089 0.893 0.823 0.881 0.826 0.862 0.824 0.856 0.827
  Histogram : 196136  2250   990   414   137    66     1     3     1     1     0     0     1

What those numbers mean, is that 200_success solution is the fastest.

Slightly slower, is my "modified" solution which I will present in a bit.

Much slower is my solution using the Stream I presented above.

Finally, pulling in, in a distant last place, is your code.

200_success -> 0.69 Microseconds
rolfl-mod   -> 0.77 Microseconds
rolfl       -> 1.55 Microseconds
FabZeros    -> 5.50 Microseconds

What is the problem with my suggestion? This code:

    input.chars().forEach(c -> sb.append(charForKey((char)c)));

If I replace that stream to instead be a for loop, it is much faster.

The rolfl-mod code replaces that stream with:

    for (int i = 0; i < input.length(); i++) {
        sb.append(charForKey(input.charAt(i)));
    }
\$\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.