7
\$\begingroup\$

I'm writing a Telephone class and it has a method called getDigits which takes in a String parameter and returns the number that would appear on your phone if you typed in those letters the old fashioned way.

Example: Typing in "CAT" would return 228.

I wrote the following code and it works but I wanted to know if anyone else out there had better ideas to do it/ more sophisticated ones. I'm learning about data abstraction/enums and maybe that's a clue to how my professor wanted me to approach this but I'm stumped.

public int getDigits(String test){
        String result = "";
        String param = test.toUpperCase();
        for(int i = 0; i<param.length(); i++){
            String s = Character.toString(param.charAt(i));
            if(s.equals("A") || s.equals("B") || s.equals("C")){
                result += 2;
            }

            else if(s.equals("D") || s.equals("E") || s.equals("F")){
                result += 3;
            }

            else if(s.equals("G") || s.equals("H") || s.equals("I")){
                result += 4;
            }

            else if(s.equals("J") || s.equals("K") || s.equals("L")){
                result += 5;
            }

            else if(s.equals("M") || s.equals("N") || s.equals("O")){
                result += 6;
            }

            else if(s.equals("P") || s.equals("Q") || s.equals("R") || s.equals("S")){
                result += 7;
            }
            else if(s.equals("T") || s.equals("U") || s.equals("V")){
                result += 8;
            }

            else if(s.equals("W") || s.equals("X") || s.equals("Y") || s.equals("Z")){
                result += 9;
            }
        }
        return Integer.parseInt(result);
    }
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to CR! Are you on Java 8? \$\endgroup\$ – h.j.k. Sep 17 '15 at 2:08
  • \$\begingroup\$ Wouldn't "CAT" be 222 28? \$\endgroup\$ – CompuChip Sep 17 '15 at 14:22
  • \$\begingroup\$ @CompuChip why would CAT be 222 28? C = 2, A = 2, T = 8, where do the other 2 2's come from? \$\endgroup\$ – Michael McGriff Sep 17 '15 at 15:25
  • 2
    \$\begingroup\$ Well back when I used to write text messages on my phone, I would have to press the ABC (2) button three times to get a C - then wait for the cursor to move to the next character, and then I could type another 2 to get A. \$\endgroup\$ – CompuChip Sep 17 '15 at 15:36
10
\$\begingroup\$

The text-to-key problem is one that has multiple solutions. The Map solution is a good one, there's nothing wrong with it. There are two other algorithms that are good too. First, though, please convert the char-to-key to a function. Having such a big loop is a problem.

public static int charToKey(char c) {
    ... do something to return key ....
}

A switch statement is similar to your cascading if's, except it is neater, and faster:

switch (c) {
    case 'A': case 'B': case 'C':
        return 2;
    case 'D': case 'E': case 'F':
        return 3;
    ....
}

Note that I abuse the layout of the switch to have multiple chars on a line.... I sometimes do that for structured inputs like this. Also, note that a case block with a return statement does not need a break - that's really nice when putting switches in to functions - just return, don't break.

A second alternative to a Map, is a mathematical function. The math one is interesting.... because it is fast. It's not that readable, though.....

Consider your keys, most keys have 3 letters, but 7 and 9 have 4 letters. If we treat Z as a special case, we can think of 9 as having just 3, which leaves only key 7 with 4 letters. Now, if we lay those letters on to a number line, where each letter occupies just... 0.32 of a span (we choose 0.32 because 4 of them is just slightly less than 1), and we organize that P is aligned with 7.0 ..... and we also take the integer value of the result... we have:

    double span = 0.32;
    double offset = 7.0 - span * ('P' - 'A');
    for (char c = 'A'; c <= 'Z'; c++) {
        double val = offset + span * (c - 'A');
        int key = (int)val;
        System.out.printf("%s -> %.3f ==> %d\n", c, val, key);
    }

and that produces:

A -> 2.200 ==> 2
B -> 2.520 ==> 2
C -> 2.840 ==> 2
D -> 3.160 ==> 3
E -> 3.480 ==> 3
F -> 3.800 ==> 3
G -> 4.120 ==> 4
H -> 4.440 ==> 4
I -> 4.760 ==> 4
J -> 5.080 ==> 5
K -> 5.400 ==> 5
L -> 5.720 ==> 5
M -> 6.040 ==> 6
N -> 6.360 ==> 6
O -> 6.680 ==> 6
P -> 7.000 ==> 7
Q -> 7.320 ==> 7
R -> 7.640 ==> 7
S -> 7.960 ==> 7
T -> 8.280 ==> 8
U -> 8.600 ==> 8
V -> 8.920 ==> 8
W -> 9.240 ==> 9
X -> 9.560 ==> 9
Y -> 9.880 ==> 9
Z -> 10.200 ==> 10

Note how all the characters have valid values, except Z. Now, there's a trick with that... which is as ugly as anything, but it works really well.... key -= key/10 - subtract an integral 10'th of the value from itself.

What does this mean? Well, it means that your function can be (for valid input):

public static int charToKey(char c) {
    int key = (int)(2.2 + (c - 'A') * 0.32);
    return key - key / 10;
}

If you want to validate the input, something like:

char uc = Character.toUpperCase(c) - 'A';
if (uc < 0 || uc >= 26) {
    return 0;
}
int key = (int)(2.20 + uc * 0.32);
return key - key / 10;

Update

Since this became a benchmarking session comparing various options, and since a new option came up in discussions with @chillworld, it seems an update is in order.

First up, I was reminded that this:

int length = text.length();
for (int i = 0; i < length; i++) {....

is faster than:

for (int i = 0; i < text.length(); i++) {....

I checked that, and, in fact, it is true. I consistently get the following benchmark times:

Task Keys -> Calc: (Unit: MILLISECONDS)
  Count    :     1000      Average  :   0.2914
  Fastest  :   0.2749      Slowest  :   2.3255
  95Pctile :   0.3327      99Pctile :   0.4448
  TimeBlock : 0.315 0.285 0.292 0.285 0.284 0.280 0.293 0.283 0.299 0.297
  Histogram :   999     0     0     1

Task Keys -> Cached: (Unit: MILLISECONDS)
  Count    :     1000      Average  :   0.2802
  Fastest  :   0.2665      Slowest  :   1.9090
  95Pctile :   0.3212      99Pctile :   0.4237
  TimeBlock : 0.298 0.275 0.284 0.276 0.276 0.269 0.284 0.274 0.283 0.284
  Histogram :   999     0     1

Where the different code paths are just:

public static int calced(String text) {
    int result = 0;
    for (int i = 0; i < text.length(); i++) {
        result *= 10;
        result += charToKey(text.charAt(i));
    }
    return result;
}

public static int cached(String text) {
    int result = 0;
    final int len = text.length();
    for (int i = 0; i < len; i++) {
        result *= 10;
        result += charToKey(text.charAt(i));
    }
    return result;
}

"Caching" the String length has a small (1% in this case) improvement in performance.

More interestingly, the idea @Chillworld had of creating a lookup array for each relevant character is much, much faster. His idea started off as:

private static final int[] cache = new int[91]; 
static { 
    cache[65] = 2; 
    cache[66] = 2; 
    cache[67] = 2; 
    cache[68] = 3; 
    cache[69] = 3; 
    cache[70] = 3; 
    ....

Essentially, build an array with a direct 1-to-1 mapping between the char value, and the phone key number.

Until this point, the fastest transform was by doing a calculation, but comparing that calculation with:

private static int cached(String text) { 
    int result = 0;
    for (int i = 0; i < text.length(); i++) {
        result *= 10;
        result += cache[text.charAt(i)];
    }
    return result;
}

Note the direct cache[text.charAt(i)] call. The cached performance (compared with the calc performance), is:

Task Keys -> Calc: (Unit: MILLISECONDS)
  Count    :     1000      Average  :   0.2914
  Fastest  :   0.2749      Slowest  :   2.3255
  95Pctile :   0.3327      99Pctile :   0.4448
  TimeBlock : 0.315 0.285 0.292 0.285 0.284 0.280 0.293 0.283 0.299 0.297
  Histogram :   999     0     0     1

Task Keys -> rawcache: (Unit: MILLISECONDS)
  Count    :     1000      Average  :   0.1425
  Fastest  :   0.1328      Slowest  :   1.7173
  95Pctile :   0.1633      99Pctile :   0.2393
  TimeBlock : 0.159 0.142 0.142 0.139 0.138 0.138 0.144 0.137 0.142 0.144
  Histogram :   998     1     0     1

Essentially it runs in half the time.

Validated

Additional thoughts about how I would make the lookup process neat, and how I would include other ideas in my answer as well as other answers, lead me to revised code with the following features:

  • fast by using a lookup
  • handles upper case, and lower case characters
  • handles the raw digits too (like 1800MyPhone)
  • returns an int array, not an int:
    • allowing for leading 0 values
    • allowing for longer-than-9-digit numbers.
  • strips off unrecognized characters

In essence, the following number 1(800)-My-Phone will translate to [1, 8, 0, 0, 6, 9, 7, 4, 6, 6, 3]

private static int switchKey(char c) {
    switch (Character.toUpperCase(c)) {
        case '0':
            return 0;
        case '1':
            return 1;
        case '2': case 'A': case 'B': case 'C':
            return 2;
        case '3': case 'D': case 'E': case 'F':
            return 3;
        case '4': case 'G': case 'H': case 'I':
            return 4;
        case '5': case 'J': case 'K': case 'L':
            return 5;
        case '6': case 'M': case 'N': case 'O':
            return 6;
        case '7': case 'P': case 'Q': case 'R': case 'S':
            return 7;
        case '8': case 'T': case 'U': case 'V':
            return 8;
        case '9': case 'W': case 'X': case 'Y': case 'Z':
            return 9;

    }
    return -1;
}

private static final int[] KEY_LOOKUP = buildLookup("ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789");

private static int[] buildLookup(String candidates) {
    int max = -1;
    for (char c : candidates.toCharArray()) {
        max = Math.max(max,
                Math.max(Character.toLowerCase(c), Character.toUpperCase(c)));
    }
    int[] lookup = new int[max + 1];
    Arrays.fill(lookup, -1);
    for (char c : candidates.toCharArray()) {
        lookup[Character.toLowerCase(c)] = switchKey(c);
        lookup[Character.toUpperCase(c)] = switchKey(c);
    }
    return lookup;
}

/**
 * Map a phone key character to a phone key number. Return -1 for invalid
 * input characters.
 * 
 * @param ch
 *            The character to convert.
 * @return the corresponding number (0 though 9), or -1 for invalid numbers
 */
public static final int lookupKey(final char ch) {
    return ch >= KEY_LOOKUP.length ? -1 : KEY_LOOKUP[ch];
}

/**
 * Parse an input string for characters that are valid phone-key characters,
 * and return the corresponding phone digits as an array.
 * 
 * @param text
 *            the text to parse for phone numbers
 * @return the valid phone digits from the input text.
 */
public static int[] parsePhoneNumber(String text) {
    final int length = text.length();
    int[] result = new int[length];
    int size = 0;
    for (int i = 0; i < length; i++) {
        int key = lookupKey(text.charAt(i));
        if (key >= 0) {
            result[size++] = key;
        }
    }
    if (size == length) {
        return result;
    }
    return Arrays.copyOf(result, size);
}
\$\endgroup\$
  • 2
    \$\begingroup\$ I'm looking forward to the benchmark! \$\endgroup\$ – 200_success Sep 17 '15 at 3:10
  • \$\begingroup\$ Have some benchmark results in the 2nd monitor - they're interesting, would love to chat about them, @200_success \$\endgroup\$ – rolfl Sep 17 '15 at 3:35
  • 3
    \$\begingroup\$ Added an update with faster lookups, and better handling for all input characters. \$\endgroup\$ – rolfl Sep 17 '15 at 13:07
  • 1
    \$\begingroup\$ pitty I can't vote twice ^^ \$\endgroup\$ – chillworld Sep 17 '15 at 14:07
7
\$\begingroup\$

This would be better done with a Map<Char Int>, with the letters as keys and the corresponding digits as values. The whole chain of if ... else if ... would then disappear and be replaced by a single, simple lookup.

Chains of if else if are almost always a bad sign in any language. In Java, sometimes switch is more appropriate, sometimes polymorphism (that is, letting the appropriate class/object decide what is right). In this case, choosing the right data structure greatly simplifies the code.

\$\endgroup\$
6
\$\begingroup\$

Aside from the excellent answers by @itsbruce and @rolfl, there's probably just one more thing to consider:

public int getDigits(String test){ ... }

Returning an int means the largest output this can return is \$2^{31} - 1\$, or 2147483647. On top of which, since we will never map to the digit 1 here, the largest output becomes much smaller. Instead of a low 10-digit number, you can only go up to 9 digits of 9, 999999999.

If you are expected to map words longer than 9 letters, consider returning a String directly. Also, as briefly mentioned in @rolfl's answer, you will also want to validate your input for uppercase-letters only, else you'll need to handle the rest separately. For example, removing non-alphanumeric letters, keep the numbers per-se and then do an uppercase conversion.

An enum-approach can be something like the following:

enum DigitMapping {
    ABC, DEF, GHI, JKL, MNO, PQRS, TUV, WXYZ;
}

Then, rely on the ordinal() method to get the mapped numbers.

\$\endgroup\$
  • \$\begingroup\$ How does using the enum help for getting the value of the key R ? \$\endgroup\$ – rolfl Sep 17 '15 at 3:44
  • \$\begingroup\$ @rolfl the approach I have in mind with that suggestion is to see if the character appears in the enum's name or not... and R is in PQRS. \$\endgroup\$ – h.j.k. Sep 17 '15 at 3:47
6
\$\begingroup\$

Note that an int is, in general, not a good way to represent phone numbers. They don't preserve leading zeroes, and they can overflow if the number has 10 digits. It would probably be more appropriate to return either a BigInteger or a String.

I found some other problems with your code:

  • The variable named param is not actually the parameter; test is. And test isn't exactly a good name for the parameter either.
  • After you do param.charAt(i) to fetch the ith character, you then needlessly convert it into a String. I would expect if (c == 'A') to be faster than if (s.equals("A")).
  • Repeated string concatenation using += is a bad idea: each time, you end up constructing a new string and copying the contents of the old string into it. That's what a StringBuilder is for.
  • Integer.parseInt() is actually mildly slow. If, against my advice above, you wanted to obtain an int, you would be better off doing arithmetic instead of string-building. (Integer.parseInt() also does that arithmetic; it's just hidden from you.)

Personally, I'd write it using an array as a lookup table — a simpler version of the Map idea.

private static final char[] DIGIT =
    "22233344455566677778889999".toCharArray();
  // ABCDEFGHIJKLMNOPQRSTUVWXYZ

public String getDigits(String letters) {
    try {
        letters = letters.toUpperCase();
        StringBuilder digits = new StringBuilder(letters.length());
        for (int i = 0; i < letters.length(); i++) {
            digits.append(DIGIT[letters.charAt(i) - 'A']);
        }
        return digits.toString();
    } catch (ArrayIndexOutOfBoundsException notLetter) {
        throw new IllegalArgumentException();
    }
}

And, if you want an int, then I suggest writing it this way:

private static final int[] NUM = {
                  2, 2, 2,    3, 3, 3,
    4, 4, 4,      5, 5, 5,    6, 6, 6,
    7, 7, 7, 7,   8, 8, 8,    9, 9, 9, 9
};

public int getNumber(String letters) {
    try {
        letters = letters.toUpperCase();
        int n = 0;
        for (int i = 0; i < letters.length(); i++) {
            n = 10 * n + NUM[letters.charAt(i) - 'A'];
        }
        return n;
    } catch (ArrayIndexOutOfBoundsException notLetter) {
        throw new IllegalArgumentException();
    }
}
\$\endgroup\$
2
\$\begingroup\$

Comparing strings

When comparing strings it's very important to specify in which Locale you want the comparison to be done. Even if it's the default locale. This makes it abundantly clear when you do and don't expect the comparison to differ between locales.

When converting to upper case without specifying the expected locale, en-US I assume, the result can be wrong when run on a JVM using another default locale, for example tr-TR.

Try this as an example:

public static void main(String[] args) {
    java.util.Locale.setDefault(java.util.Locale.forLanguageTag("tr-TR"));
    String test = "ghi";
    int expected = 444;
    int actual = getDigits(test);
    boolean result = expected == actual;
    System.out.println("Result: " + 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.