3
\$\begingroup\$

What would be the most performant way to get the last 2 digits of a string?

For example: getLastTwoDigits("a1b2cd3e4ghi5jk") must return "45";

I had already asked how to get the first two digits of a string. But now I need a performant way to get the last two digits.

I've adapted the answer I received in the other question and I could make it work using the code below. However, I know that I've defeated the purpose of StringBuilder when I used sb.insert(0, char).

private static String getLastTwoDigits(String s) {
    if(s==null)
        return null;

    StringBuilder sb = new StringBuilder(2);

    char charArray[] = s.toCharArray();
    for (int i = charArray.length-1; i>=0; i--) {
        if (Character.isDigit(charArray[i])) {
            sb.insert(0, charArray[i]);
            if (sb.length() == 2)
                break;
        }
    }

    return sb.toString();
}

I imagine that StringBuider is not the right tool for this case. So what would be the most performant solution?

\$\endgroup\$
2
\$\begingroup\$

Don't worry about performance until you've proved that you have a performance problem. Make your code readable and maintainable. A stream would solve this nicely.

Stream<char> digits = 
    s.toCharArray().stream()
    .filter(c -> Character.isDigit(c));

Stream<String> end = digits.skip(digits.size() - 2)
        .map(c -> Character.toString(c));

return end.collect(Collectors.joining(""));

Or with a little syntax sugar to make it a little less verbose.

Stream<char> digits = 
    s.toCharArray().stream()
    .filter(Character::isDigit);

return digits.skip(digits.size() - 2)
        .map(Character::toString)
        .collect(Collectors.joining(""));

Untested. May not compile.

\$\endgroup\$
  • 1
    \$\begingroup\$ FYI - Stream<char> won't work. Use Stream<Character>, as generics do not support primitives as type arguments. \$\endgroup\$ – Tamoghna Chowdhury Jun 30 '17 at 6:29
3
\$\begingroup\$
            sb.insert(0, charArray[i]);
            if (sb.length() == 2)
                break;
        }
    }

    return sb.toString();

You could change this to

             sb.append(charArray[i]);
             if (sb.length() >= digitCount) {
                 break;
             }
         }
     }

     return sb.reverse().toString();

Then you're using your StringBuilder as intended. Appending rather than constantly inserting.

Changing 2 to digitCount allows you to alter the number of digits to find easily.

I prefer to always use the block form of control structures, even when the statement form would work.

\$\endgroup\$
2
\$\begingroup\$

Your question involves two tasks, extracting digits and reversing their order. One of the standard ways to reverse the order of something is to use a stack, which is a LIFO (Last In First Out) structure. Go through the target string, rejecting non-digits and putting digits on the stack. Then pop the last two entries off the top of the stack. I have added extra code to deal with the cases of only one digit or no digits.

In general it is not good to return null from any method; it is better to throw an exception. I am not sure if you have covered exceptions yet, but when you do you should return to this code and use them in place of the two null returns.

As a very minor point, your first if omitted the space between the if and the first parenthesis. Omitting the space indicates a method call. With language structures: if, for etc. distinguish them by including the space as a separator.

import java.util.Stack;

private static String getLastTwoDigits(String s) {

    if (s == null) {
        return null;  // or throw exception.
    }

    // 1. Extract the digits.
    Stack<Character> digiStack = new Stack<>();

    char charArray[] = s.toCharArray();
    for (Character c : charArray) {
        if (Character.isDigit(c)) {
            digiStack.push(c);
        }
    }

    // 2. Return last two digits in original order.
    if (digiStack.size() >= 2) {
        StringBuilder sb = new StringBuilder(2);

        sb.append(digiStack.pop());
        sb.append(digiStack.pop());

        return sb.reverse().toString();
    } else if (digiStack.size() == 1) {
        return digiStack.pop().toString();
    } else {
        // No digits found.
        return null;  // or throw exception.
    }

} // end getLastTwoDigits()
\$\endgroup\$
1
\$\begingroup\$

If you want to get out the minimum of executed machine instructions, you should go the following route, which replaces the StringBuilder with an array digits and an index di into that array.

The array is filled from the end to the beginning, and the index always points behind the next free element of the array.

String getLastTwoDigits(String s) {
  char[] digits = new char[2];
  int di = 2;
  for (int si = s.length() - 1; si >= 0; si--) {
    char c = s.charAt(i);
    if (Character.isDigit(c)) {
      di--;
      digits[di] = c;
      if (di == 0) {
        break;
      }
    }
  }
  return new String(digits, di, 2 - di);
}

To see whether the generated machine code is really worth to write this complicated low-level code, look at the generated machine code using +XX:PrintAssembly, comparing it with the other solutions. And measure the execution time in a reliable benchmark (JMH).

\$\endgroup\$
1
\$\begingroup\$

This compiles.
Generics do not support primitives.
Arrays do not have a method stream().
Streams do not have a method size().
Sadly toString() is ambiguous on Character.

List<Character> digits = s.chars()
            .mapToObj(i -> (char) i)
            .filter(Character::isDigit)
            .collect(Collectors.toList());

String lastTwoDigits = digits.stream()
            .skip(digits.size() - 2)
            .map(String::valueOf)
            .collect(Collectors.joining());
\$\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.