Java убрать повторяющиеся символы
- replace(char oldChar, char newChar):String
- replace(CharSequence target, CharSequence replacement):String
- replaceAll(String regex,String replacement):String
- replaceFirst(String regex,String replacement):String
String text = "keeshh"; String result = text.replaceAll("([a-z])\\1", ""); System.out.println(result);//"ks" String text = "keeshhs"; int len; do< len = text.length();//сохраняем длину строки text = text.replaceAll("([a-z])\\1", ""); >while(len != text.length());//сравниваем новую длину строки с сохраненной длиной System.out.println(text);//"k" String text = "keeeeshh"; text = text.replaceAll("([a-z])\\1+", ""); System.out.println(text);//"ks" String text = "kkeesshh"; text = text.replaceAll("([a-z])\\1", "$1"); System.out.println(text);//"kesh" Для замены мы использовали выражение $1, которое говорит о том, что текст, соответствующий регулярному выражению, необходимо заменить на текст, соответствующий группировке с номером 1. В нашем случае группировка с номером — это текст, соответствующий шаблону [a-z]. Можно переписать код, используя группу с номером 2 для замены:
String text = "kkeesshh"; text = text.replaceAll("([a-z])(\\1)", "$2"); System.out.println(text);//"kesh" String text = "keeeeessshh"; text = text.replaceAll("([a-z])\\1+", "$1"); System.out.println(text);//"kesh" Удаление повторяющихся символов из строки
В этом руководстве мы обсудим несколько техник в Java, позволяющих удалить повторяющиеся символы из строки.
Для каждого методаwe’ll also talk briefly about its time and space complexity.
2. Используяdistinct
Начнем с удаления дубликатов из нашей строки с помощью методаdistinct, представленного в Java 8.
Ниже мы получаем экземплярIntStream из заданного строкового объекта. Затем мы используем методdistinct для удаления дубликатов. Наконец, мы вызываем методforEach, чтобы перебрать отдельные символы и добавить их к нашемуStringBuilder:
StringBuilder sb = new StringBuilder(); str.chars().distinct().forEach(c -> sb.append((char) c));Time Complexity: O(n) — время выполнения цикла прямо пропорционально размеру входной строки
Auxiliary Space:O(n) — посколькуdistinct используетLinkedHashSet внутри, и мы также сохраняем полученную строку в объектеStringBuilder
Maintains Order: Да — посколькуLinkedHashSet сохраняет порядок своих элементов
И хотя приятно, что Java 8 так хорошо справляется с этой задачей, давайте сравним ее с нашими собственными усилиями.
3. ИспользуяindexOf
Наивный подход к удалению дубликатов из строки просто включаетlooping over the input and using the indexOf method to check whether the current character already exists in the resulting string:
StringBuilder sb = new StringBuilder(); int idx; for (int i = 0; i < str.length(); i++) < char c = str.charAt(i); idx = str.indexOf(c, i + 1); if (idx == -1) < sb.append(c); >>Time Complexity: O(n * n) — для каждого символа методindexOf пробегает оставшуюся строку
Auxiliary Space:O(n) — требуется линейное пространство, поскольку мы используемStringBuilder для хранения результата
Maintains Order: Да
Этот метод имеет ту же пространственную сложность, что и первый подход, ноperforms much slower.
4. Использование массива символов
Мы также можем удалить дубликаты из нашей строки с помощьюconverting it into a char array and then looping over each character and comparing it to all subsequent characters.
Как видно ниже, мы создаем два циклаfor и проверяем, повторяется ли каждый элемент в строке. Если найден дубликат, мы не добавляем его вStringBuilder:
char[] chars = str.toCharArray(); StringBuilder sb = new StringBuilder(); boolean repeatedChar; for (int i = 0; i < chars.length; i++) < repeatedChar = false; for (int j = i + 1; j < chars.length; j++) < if (chars[i] == chars[j]) < repeatedChar = true; break; >> if (!repeatedChar) < sb.append(chars[i]); >>Time Complexity: O(n * n) — у нас есть внутренний и внешний цикл, проходящие по входной строке
Auxiliary Space:O(n) — требуется линейное пространство, поскольку переменнаяchars хранит новую копию введенной строки, и мы также используемStringBuilder для сохранения результата
Maintains Order: Да
Опять же, наша вторая попытка работает плохо по сравнению с предложением Core Java, но давайте посмотрим, что мы получим с нашей следующей попыткой.
5. Использование сортировки
Кроме того, повторяющиеся символы могут быть устранены путем сортировки нашей входной строки для группировки дубликатов. In order to do that, we have to convert the string to a char array and sort it using the Arrays.sort method. Finally, we’ll iterate over the sorted char array.с
На каждой итерации мы будем сравнивать каждый элемент массива с предыдущим элементом. Если элементы разные, мы добавим текущий символ кStringBuilder:
StringBuilder sb = new StringBuilder(); if(!str.isEmpty()) < char[] chars = str.toCharArray(); Arrays.sort(chars); sb.append(chars[0]); for (int i = 1; i < chars.length; i++) < if (chars[i] != chars[i - 1]) < sb.append(chars[i]); >> >Time Complexity: O(n log n) — сортировка используетdual-pivot Quicksort, который предлагает производительность O (n log n) для многих наборов данных
Auxiliary Space:O(n) — поскольку методtoCharArray делает копию вводаString
Maintains Order: Нет
Давайте попробуем еще раз в нашей последней попытке.
6. ИспользуяSet
Другой способ удалить повторяющиеся символы из строки — использоватьSet. If we do not care about the order of characters in our output string we can use a HashSet.Otherwise, we can use a LinkedHashSet to maintain the insertion order.
В обоих случаях мы перебираем строку ввода и добавляем каждый символ кSet. После того, как символы будут вставлены в набор, мы будем перебирать их, чтобы добавить их в песокStringBuilder и вернуть результирующую строку:
StringBuilder sb = new StringBuilder(); Set linkedHashSet = new LinkedHashSet<>(); for (int i = 0; i < str.length(); i++) < linkedHashSet.add(str.charAt(i)); >for (Character c : linkedHashSet)
Time Complexity: O(n) — время выполнения цикла прямо пропорционально размеру входной строки
Auxiliary Space:O(n) — пространство, необходимое дляSet, зависит от размера входной строки; также мы используемStringBuilder для хранения результата
Maintains Order:LinkedHashSet – Да,HashSet – Нет
И теперь мы подошли к подходу Core Java! Неудивительно, что это очень похоже на то, что уже делаетdistinct.
7. Заключение
In this article, we covered a few ways to remove repeated characters from a string in Java. Мы также рассмотрели временную и пространственную сложность каждого из этих методов.
Как всегда, фрагменты кода можно найтиover on GitHub.
Как убрать повторяющиеся символы из строки в java
В этой статье мы научимся проверять слова на повторяющиеся символы, а также заменять и удалять найденные дубли. Это мы будет делать с помощью специального алгоритма, который сейчас и реализуем на Java.
Удаление повторяющихся символов из строки. Теория
Сегодня мы реализуем интересный метод, который принимают на вход строку, например, «jjjj», а на выходе выдает «j». Для этого мы не будет использовать сторонние библиотеки, а сделаем все на чистой Java.
Алгоритм удаления повторяющихся символом в строке мы реализуем в методе deleteDuplicates (String input), который принимает в качестве параметра строку с дублями и возвращает новую строку без дублей.
Суть алгоритма сводится к тому, что мы проходим по каждому символу строки и проверяем, не является ли он дубликатом уже найденного символа. Если он таким является, то вместо него вставляем 0. Так продолжается, пока мы не пройдем в цикле всю строку до конца. После цикла вызывается метод, который создает строку из массива символов, пропуская символы с нулями. Этот метод будет работать даже если входная строка содержит более одного повторяющегося символа. Такой алгоритм является brute force алгоритмом (т.н. полный перебор или метод «грубой силы»).
Как убрать повторяющиеся символы из строки. Практика
Ниже представлен метод удаления символов-дублей из входной строки:
Удаление повторяющихся символов из строки
Откройте для себя различные методы удаления повторяющихся символов из строки в Java.
1. Обзор
В этом уроке мы обсудим несколько методов в Java о том, как удалить повторяющиеся символы из строки.
Для каждой техники мы также кратко расскажем о ее сложности во времени и пространстве.
2. Использование различных
Давайте начнем с удаления дубликатов из вашей строки с помощью метода distinct , представленного в Java 8.
Ниже мы получаем экземпляр Int S stream из данного строкового объекта. Затем мы используем метод distinct для удаления дубликатов. Наконец, мы вызываем метод forEach , чтобы перебрать отдельные символы и добавить их в наш StringBuilder :
StringBuilder sb = new StringBuilder(); str.chars().distinct().forEach(c -> sb.append((char) c));
Временная сложность: O(n) – время выполнения цикла прямо пропорционально размеру входной строки
Вспомогательное пространство: |/O(n) – поскольку distinct использует LinkedHashSet внутренне, и мы также храним полученную строку в объекте StringBuilder
Поддерживает порядок: Да – так как LinkedHashSet поддерживает порядок своих элементов
И хотя приятно, что Java 8 так хорошо справляется с этой задачей, давайте сравним ее с усилиями по созданию нашей собственной.
3. Использование indexOf
Наивный подход к удалению дубликатов из строки просто включает в себя перебор входных данных и использование метода indexOf для проверки того, существует ли текущий символ уже в результирующей строке :
StringBuilder sb = new StringBuilder(); int idx; for (int i = 0; i < str.length(); i++) < char c = str.charAt(i); idx = str.indexOf(c, i + 1); if (idx == -1) < sb.append(c); >>
Временная сложность: O(n * n) – для каждого символа метод indexOf проходит через оставшуюся строку
Вспомогательное пространство: O(n) – требуется линейное пространство, так как мы используем StringBuilder для хранения результата
Поддерживает порядок: Да
Этот метод имеет ту же пространственную сложность, что и первый подход, но работает намного медленнее.
4. Использование массива символов
Мы также можем удалить дубликаты из нашей строки, преобразовав ее в массив char , а затем зациклившись на каждом символе и сравнив его со всеми последующими символами .
Как мы видим ниже, мы создаем два цикла для и проверяем, повторяется ли каждый элемент в строке. Если дубликат найден, мы не добавляем его в StringBuilder :
char[] chars = str.toCharArray(); StringBuilder sb = new StringBuilder(); boolean repeatedChar; for (int i = 0; i < chars.length; i++) < repeatedChar = false; for (int j = i + 1; j < chars.length; j++) < if (chars[i] == chars[j]) < repeatedChar = true; break; >> if (!repeatedChar) < sb.append(chars[i]); >>
Временная сложность: O(n * n) – у нас есть внутренний и внешний цикл, проходящие через входную строку
Вспомогательное пространство: O(n) – требуется линейное пространство, так как переменная chars хранит новую копию строкового ввода, и мы также используем StringBuilder для сохранения результата
Поддерживает порядок: Да
Опять же, наша вторая попытка работает плохо по сравнению с основным предложением Java, но давайте посмотрим, к чему мы придем с нашей следующей попыткой.
5. Использование сортировки
Кроме того, повторяющиеся символы могут быть устранены путем сортировки нашей входной строки для группирования дубликатов. Для этого мы должны преобразовать строку в char a rray и отсортировать ее с помощью Массивов . сортировка метод . Наконец, мы проведем итерацию по отсортированному массиву char .
Во время каждой итерации мы будем сравнивать каждый элемент массива с предыдущим элементом. Если элементы отличаются, мы добавим текущий символ в StringBuilder:
StringBuilder sb = new StringBuilder(); if(!str.isEmpty()) < char[] chars = str.toCharArray(); Arrays.sort(chars); sb.append(chars[0]); for (int i = 1; i < chars.length; i++) < if (chars[i] != chars[i - 1]) < sb.append(chars[i]); >> >
Временная сложность: O(n log n) – сортировка использует быструю сортировку с двойным поворотом , которая обеспечивает производительность O(n log n) для многих наборов данных
Вспомогательное пространство: |/O(n) – так как метод toCharArray создает копию входной строки
Поддерживает порядок: Нет
Давайте попробуем еще раз с нашей последней попыткой.
6. Использование набора
Другим способом удаления повторяющихся символов из строки является использование Set . Если нас не волнует порядок символов в нашей выходной строке, мы можем использовать HashSet . В противном случае мы можем использовать LinkedHashSet для поддержания порядка вставки.
В обоих случаях мы будем перебирать входную строку и добавлять каждый символ в Set . Как только символы будут вставлены в набор, мы повторим его, чтобы добавить их в StringBuilder и вернуть полученную строку:
StringBuilder sb = new StringBuilder(); Set linkedHashSet = new LinkedHashSet<>(); for (int i = 0; i < str.length(); i++) < linkedHashSet.add(str.charAt(i)); >for (Character c : linkedHashSet)
Временная сложность: O(n) – время выполнения цикла прямо пропорционально размеру входной строки
Вспомогательное пространство: |/O(n) – пространство, необходимое для набора , зависит от размера входной строки; кроме того, мы используем StringBuilder для хранения результата
Поддерживает порядок: |/LinkedHashSet – Да, HashSet – Нет
И теперь мы соответствуем основному подходу Java! Не очень шокирует, что это очень похоже на то, что уже делает distinct .
7. Заключение
В этой статье мы рассмотрели несколько способов удаления повторяющихся символов из строки в Java. Мы также посмотрели на время и пространство
В этой статье мы рассмотрели несколько способов удаления повторяющихся символов из строки в Java. Мы также посмотрели на время и пространство