Строка повторяющихся символов java

Удаление повторяющихся символов из строки

Откройте для себя различные методы удаления повторяющихся символов из строки в 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. Мы также посмотрели на время и пространство

Источник

Поиск повторяющихся символов в строке на Java

Ниже приведен пример Java, который ищет и удаляет повторяющиеся символы из заданной строки.

Пример

import java.util.Arrays; import org.apache.commons.lang3.ArrayUtils; public class DuplicateSample < public static void main(String args[])< String str = "malayalam"; char[] myArray = str.toCharArray(); for(int i=0; i> > System.out.println("String value after deleting the duplicate values :"+Arrays.toString(myArray)); > >

Итог

String value after deleting the duplicate values :[m, a, l, y]

Эти символы можно найти с помощью вложенного цикла for. Пример этого приведен ниже:

В приведенной выше строке p является повторяющимся символом, так как встречается более одного раза.

Пример

Вывод

The string is:beautiful beach Duplicate Characters in above string are: b e a u

Сначала определяется строка str. Затем str.toCharArray() преобразует строку в последовательность символов. Исходная строка отображается. Фрагмент кода, демонстрирующий это, приведен ниже:

String str = "beautiful beach"; char[] carray = str.toCharArray(); System.out.println("The string is:" + str);

Дублирующиеся символы находятся в строке с использованием вложенного цикла for. Затем эти символы отображаются.

System.out.print("Duplicate Characters in above string are: "); for (int i = 0; i < str.length(); i++) < for (int j = i + 1; j < str.length(); j++) < if (carray[i] == carray[j]) < System.out.print(carray[j] + " "); break; >> >

Средняя оценка 3.5 / 5. Количество голосов: 11

Спасибо, помогите другим — напишите комментарий, добавьте информации к статье.

Видим, что вы не нашли ответ на свой вопрос.

Напишите комментарий, что можно добавить к статье, какой информации не хватает.

Источник

Как убрать повторяющиеся символы из строки в java

В этой статье мы научимся проверять слова на повторяющиеся символы, а также заменять и удалять найденные дубли. Это мы будет делать с помощью специального алгоритма, который сейчас и реализуем на Java.

Удаление повторяющихся символов из строки. Теория

Сегодня мы реализуем интересный метод, который принимают на вход строку, например, «jjjj», а на выходе выдает «j». Для этого мы не будет использовать сторонние библиотеки, а сделаем все на чистой Java.

Алгоритм удаления повторяющихся символом в строке мы реализуем в методе deleteDuplicates (String input), который принимает в качестве параметра строку с дублями и возвращает новую строку без дублей.

Суть алгоритма сводится к тому, что мы проходим по каждому символу строки и проверяем, не является ли он дубликатом уже найденного символа. Если он таким является, то вместо него вставляем 0. Так продолжается, пока мы не пройдем в цикле всю строку до конца. После цикла вызывается метод, который создает строку из массива символов, пропуская символы с нулями. Этот метод будет работать даже если входная строка содержит более одного повторяющегося символа. Такой алгоритм является brute force алгоритмом (т.н. полный перебор или метод «грубой силы»).

Как убрать повторяющиеся символы из строки. Практика

Ниже представлен метод удаления символов-дублей из входной строки:

Источник

Удаление повторяющихся символов из строки

В этом руководстве мы обсудим несколько техник в 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.

Источник