Реализация алгоритма RLE для строки

425

02 апреля 2017, 02:25

Тренирую работу с классом String. Стоит задача по RLE:

На вход подается строка (допустим, Jjjjaavvva). Результатом должно быть Jj4a2v3a.
Макс. количество повторов - 9. Для aaaaaaaaaa (10 букв a) это должно записываться как a9a1.

Я думаю пробежаться по массиву этой строки и где есть совпадения сделать substring этой области и split, а потом считать кол-во и делать конкатенацию.

Как это реализовать лучше? Может, есть готовые решения?

Answer 1

Достаточно пройти один раз по всем символам строки и собрать новую строку в StringBuilder.

При просмотре очередного символа идёт проверка:

если достигнут конец строки, или текущий символ встретился уже 9 раз подряд, или очередной символ не равен текущему, то записываем текущий символ и количество его повторений в результат, в качестве текущего символа устанавливаем очередной, а количество повторений - в 1.
иначе увеличиваем количество повторений на 1.

Код реализации:

public static String getRLE(String str)
{
    if (str == null || str.equals(""))
    {
        return str;
    }
    char currentChar = str.charAt(0);
    int currentCharCount = 1;
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= str.length(); i++)
    {
        char c = i < str.length() ? str.charAt(i) : 0;
        if (i == str.length() || currentCharCount == 9 || c != currentChar)
        {
            sb.append(currentChar);
            sb.append((char)(currentCharCount + '0'));
            currentCharCount = 1;
            currentChar = c;
        }
        else
        {
            currentCharCount++;
        }
    }
    return sb.toString();
}

Для строки aaaaaaaaaabbbccca результатом будет a9a1b3c3a1.