1. Información general
En este tutorial, discutiremos varias técnicas en Java sobre cómo eliminar caracteres repetidos de una cadena.
Para cada técnica, también hablaremos brevemente sobre su complejidad temporal y espacial.
2. Usando distintos
Comencemos por eliminar los duplicados de nuestra cadena utilizando el método distinto introducido en Java 8.
A continuación, obtenemos una instancia de un Int S tream de un objeto de cadena dado. Luego, usamos el método distinto para eliminar los duplicados. Finalmente, llamamos al método forEach para recorrer los distintos caracteres y agregarlos a nuestro StringBuilder :
StringBuilder sb = new StringBuilder(); str.chars().distinct().forEach(c -> sb.append((char) c));Complejidad de tiempo: O (n) - el tiempo de ejecución del bucle es directamente proporcional al tamaño de la cadena de entrada
Espacio auxiliar: O (n) - dado que distintos usa un LinkedHashSet internamente y también estamos almacenando la cadena resultante en un objeto StringBuilder
Mantiene el orden: Sí, ya que LinkedHashSet mantiene el orden de sus elementos
Y, si bien es bueno que Java 8 haga esta tarea tan bien por nosotros, comparémoslo con los esfuerzos para desarrollar el nuestro.
3. Usando indexOf
El enfoque ingenuo para eliminar duplicados de una cadena simplemente implica recorrer la entrada y usar el método indexOf para verificar si el carácter actual ya existe en la cadena resultante :
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); } } Complejidad de tiempo: O (n * n) - para cada carácter, el método indexOf se ejecuta a través de la cadena restante
Espacio auxiliar: O (n) : se requiere espacio lineal ya que estamos usando StringBuilder para almacenar el resultado
Mantiene el orden: Sí
Este método tiene la misma complejidad de espacio que el primer enfoque, pero funciona mucho más lento.
4. Usando una matriz de caracteres
También podemos eliminar duplicados de nuestra cadena mediante su conversión en un Char matriz y luego recorrer distintos caracteres y comparándolo con todos los caracteres subsiguientes .
Como podemos ver a continuación, estamos creando dos bucles for y comprobando si cada elemento se repite en la cadena. Si se encuentra un duplicado, no lo adjuntamos al 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]); } } Complejidad de tiempo: O (n * n) : tenemos un bucle interno y otro externo que atraviesan la cadena de entrada
Espacio auxiliar: O (n) : se requiere espacio lineal ya que la variable chars almacena una nueva copia de la entrada de la cadena y también estamos usando StringBuilder para guardar el resultado
Mantiene el orden: Sí
Nuevamente, nuestro segundo intento funciona mal en comparación con la oferta Core Java, pero veamos a dónde llegamos con nuestro próximo intento.
5. Uso de la clasificación
Alternativamente, los caracteres repetidos se pueden eliminar ordenando nuestra cadena de entrada para agrupar los duplicados. Para hacer eso, tenemos que convertir la cadena a char a rray y ordenarla usando Arrays . método de clasificación . Por último, vamos a iterar sobre la ordenada carbón matriz.
Durante cada iteración, compararemos cada elemento de la matriz con el elemento anterior. Si los elementos son diferentes, agregaremos el carácter actual al 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]); } } }Complejidad de tiempo: O (n log n) : la clasificación utiliza un Quicksort de doble pivote que ofrece un rendimiento O (n log n) en muchos conjuntos de datos
Espacio auxiliar: O (n) - ya que el método toCharArray hace una copia de la cadena de entrada
Mantiene el orden: No
Intentémoslo de nuevo con nuestro último intento.
6. Usando un juego
Otra forma de eliminar caracteres repetidos de una cadena es mediante el uso de un conjunto . Si no nos importa el orden de los caracteres en nuestra cadena de salida, podemos usar un HashSet . De lo contrario, podemos usar un LinkedHashSet para mantener el orden de inserción.
En ambos casos, recorreremos la cadena de entrada y agregaremos cada carácter al conjunto . Una vez que los caracteres se insertan en el conjunto, iteraremos sobre él para agregarlos al StringBuilder y devolver la cadena resultante:
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) { sb.append(c); } Complejidad de tiempo: O (n) - el tiempo de ejecución del bucle es directamente proporcional al tamaño de la cadena de entrada
Espacio auxiliar: O (n) - el espacio requerido para el conjunto depende del tamaño de la cadena de entrada; Además, estamos usando StringBuilder para almacenar el resultado.
Mantiene el orden: LinkedHashSet - Sí, HashSet - No
¡Y ahora, hemos igualado el enfoque de Core Java! No es muy sorprendente descubrir que esto es muy similar a lo que ya hace distinto .
7. Conclusión
En este artículo, cubrimos algunas formas de eliminar caracteres repetidos de una cadena en Java. También analizamos la complejidad temporal y espacial de cada uno de estos métodos.
Como siempre, los fragmentos de código se pueden encontrar en GitHub.