0

Пытаюсь обойти строку и последовательно удалять дубликаты букв.

ABBACBAABCB-->AACBAABCB-->CBAABCB-->CBBCB-->CCB-->B

Идея в том, чтобы обходить символы в строке и удалять дубликаты внутри цикла do-while.

class Main {
    public static String list = "ABBACBAABCB";
    public static boolean notvalid = true;

    public static void main(String[] args) {
        do {
            String r = Itterate(list);
            isvalid(r);
            //list = r does not work
        } while (notvalid);

    }

    public static String Itterate(String str) {
        for (int i = 1; i < list.length(); i = i + 1) {
            char Curr = list.charAt(i);
            char Prev = list.charAt(i - 1);
            if (Curr == Prev) {
                String results = str.substring(0, i - 1)
                        + str.substring(i, str.length());
                return results;
            }
        }
        return str;
    }

    public static void isvalid(String str) {
        for (int i = 1; i < str.length(); i = i + 1) {
            char curr = str.charAt(i);
            char prev = str.charAt(i - 1);
            if (curr == prev) {
                notvalid = true;
                return;
            }
        }
        notvalid = false;
        return;
    }
}

Понятно, что это не работает, это просто бесконечный цикл.

Из чего я сделал вывод, что нельзя выполнить list = results в java, так как string неизменяемы.

Как это можно сделать в Java?

1
  • Простой многопроходный алгоритм решает задачу за квадрат от длины строки. Кажется можно решить за линейное время. Какая будет нужна дополнительная память? 6 апр 2021 в 13:54

3 ответа 3

1

А зачем так сложно? Может я чего-то не понял, но вроде это достаточно тривиальная задача и решается довольно просто:

public static String removeDuplicateSymbols(String phrase) {
    int length = 0;
    while (true) {
        StringBuilder sb = new StringBuilder();
        char[] arr = phrase.toCharArray();
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] != arr[i + 1]) sb.append(arr[i]);
        }
        String result = sb.append(arr[arr.length - 1]).toString();
        if (result.length() == length) return result;
        length = result.length();
    }
}
5
  • ABBA должна быть преобразована в пустую строку. Ваше решение выдаст не пустую. 6 апр 2021 в 13:58
  • @Stanislav Volodarskiy Пытаюсь обойти строку и последовательно удалять дубликаты букв. - это же вы написали. я и удалил все дубликаты букв, стоящих погследовательно 6 апр 2021 в 19:31
  • Прочитайте внимательно пример в начале вопроса. Процедуру удаления нужно применять многократно. 6 апр 2021 в 19:32
  • @Stanislav Volodarskiy прочитал и все равно до вашего комментария идеи не понял. хотя по большому счету сделать из моего решения то, что нужно вам - вопрос 15 секунд. ответ исправил 6 апр 2021 в 19:44
  • Да, это оно. Спасибо. 6 апр 2021 в 20:04
0

Можно использовать regexp и один цикл do-while:

String str = "ABBACBAABCB";

do {
    System.out.println(str);
} while (!str.equals(str = str.replaceFirst("(.)\\1", "")));

Вывод:

ABBACBAABCB
AACBAABCB
CBAABCB
CBBCB
CCB
B

Подробно:

  • regexp (.)\\1 - любой символ, за который следует такой же символ;
  • str = str.replaceFirst(...) - последовательно удаяет дубликаты один за одним и заменяет текущую строку;
  • !str.equals(...) - проверяет неравенство текущей строки самой себе, только без дубликатов.
0

Ваш алгоритм работает. Добавлена печать промежуточных результатов, раскомментировано присвоение list = r и исправлена ошибка в составлении новой строки (удалялся только один символ из пары):

6a7
>             System.out.println(list);
9c10
<             //list = r does not work
---
>             list = r;
11c12
< 
---
>         System.out.println(list);
20c21
<                         + str.substring(i, str.length());
---
>                         + str.substring(i + 1, str.length());

Почему у вас не работало, я не понимаю. Могу только предположить что вы смотрели результаты в отладчике и куда-то не туда посмотрели. Всё работает как надо:

$ javac Main.java && java Main
ABBACBAABCB
AACBAABCB
CBAABCB
CBBCB
CCB
B

Хотя всё работает, есть вещи которые должны быть исправлены. Функция Itterate работает нормально только если её вызывать с аргументом list. В её теле перемешаны обращения к list и к str. Не следовало пользоваться глобальными переменными - в данном случае list.

Метод isvalid работает правильно, но использует глобальную переменную notvalid. Кроме того он не нужен. Функцию Itterate можно вызвать в цикле до тех пор пока длина строки сокращается.

Вот ваш код почищенный и отглаженный (в частности Itterate стала ReduceOnce):

class Main {
    public static void main(String[] args) {
        Reduce("ABBACBAABCB");
    }

    public static String Reduce(String s) {
        for (; ; ) {
            System.out.println(s);
            String s2 = ReduceOnce(s);
            if (s2.length() == s.length()) {
                break;
            }
            s = s2;
        }
        return s;
    }

    public static String ReduceOnce(String s) {
        for (int i = 1; i < s.length(); ++i) {
            if (s.charAt(i - 1) == s.charAt(i)) {
                return s.substring(0, i - 1) + s.substring(i + 1, s.length());
            }
        }
        return s;
    }
}

Есть ещё одна вещь которую можно доработать - алгоритм. Текущее решение решение работает за время пропорциональное квадрату длины строки в худшем случае. А можно решить задачу за линейное время с помощью стека.

Символы строки накапливаются в стеке. Если следущий символ совпадает с вершиной стека, то вершина удаляется и символ тоже отбрасывается. Если совпадения нет, то символ добавляется в стек. По окончании цикла ответ в стеке:

import java.util.Stack;

class ReduceString {
    public static void main(String[] args) {
        System.out.println(Reduce("ABBACBAABCB"));
    }

    public static String Reduce(String s) {
        Stack<Character> stack = new Stack<Character>();

        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (!stack.empty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }

        StringBuilder sb = new StringBuilder(stack.size());
        for (char c : stack) {
            sb.append(c);
        }
        return sb.toString();
    }
}

Вот как выглядит обработка строки ABBACBAABCB с помощью стека:

[    ] <- A
[A   ] <- B
[AB  ] <- B
[A   ] <- A
[    ] <- C
[C   ] <- B
[CB  ] <- A
[CBA ] <- A
[CB  ] <- B
[C   ] <- C
[    ] <- B
[B   ]

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.