Determinar que una cadena tiene todos caracteres únicos sin utilizar estructuras de datos adicionales y sin el supuesto de caracteres en minúsculas

Question

Esta es una de las preguntas del Descifrando la entrevista de codificación libro por Gayle Laakmann McDowell:

Implemente un algoritmo para determinar si una cadena tiene todos caracteres únicos.¿Qué pasa si no puede utilizar estructuras de datos adicionales?

El autor escribió:

Podemos reducir un poco nuestro uso de espacio usando un vector de bits.Asumiremos, en el siguiente código, que la cadena está solo en minúsculas 'a' a través de 'z'.Esto nos permitirá usar solo un int.

El autor tiene esta implementación:

public static boolean isUniqueChars(String str) {
    int checker = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i) - 'a';
        if ((checker & (1 << val)) > 0)
            return false;
        checker |= (1 << val);
    }
    return true;
}

Digamos que nos deshacemos de la suposición de que "la cadena está solo en minúsculas 'a' a través de 'z'".En cambio, la cadena puede contener cualquier tipo de carácter, como caracteres ASCII o Unicode.

¿Existe una solución tan eficiente como la del autor (o una solución que se acerque a ser tan eficiente como la del autor)?

Preguntas relacionadas:

• Detectar si una cadena tiene caracteres únicos:¿Comparando mi solución con "Descifrar la entrevista de codificación?"
• Explicar el uso de un vector de bits para determinar si todos los caracteres son únicos.
• Cadena de caracteres únicos
• Implementación de un algoritmo para determinar si una cadena tiene todos los caracteres únicos
• determinar si una cadena tiene todos los caracteres únicos?

Answer 1

Para el conjunto de caracteres ASCCII puede representar las 256bits en 4 largos: usted básicamente un código de mano es una matriz.

public static boolean isUniqueChars(String str) {
    long checker1 = 0;
    long checker2 = 0;
    long checker3 = 0;
    long checker4 = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i);
        int toCheck = val / 64;
        val %= 64;
        switch (toCheck) {
            case 0:
                if ((checker1 & (1L << val)) > 0) {
                    return false;
                }
                checker1 |= (1L << val);
                break;
            case 1:
                if ((checker2 & (1L << val)) > 0) {
                    return false;
                }
                checker2 |= (1L << val);
                break;
            case 2:
                if ((checker3 & (1L << val)) > 0) {
                    return false;
                }
                checker3 |= (1L << val);
                break;
            case 3:
                if ((checker4 & (1L << val)) > 0) {
                    return false;
                }
                checker4 |= (1L << val);
                break;
        }            
    }
    return true;
}

Puede usar el siguiente código para generar el cuerpo de un método similar para los caracteres Unicode:

static void generate() {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < 1024; i++) {
        sb.append(String.format("long checker%d = 0;%n", i));
    }
    sb.append("for (int i = 0; i < str.length(); ++i) {\n"
            + "int val = str.charAt(i);\n"
            + "int toCheck = val / 64;\n"
            + "val %= 64;\n"
            + "switch (toCheck) {\n");
    for (int i = 0; i < 1024; i++) {
        sb.append(String.format("case %d:\n"
                + "if ((checker%d & (1L << val)) > 0) {\n"
                + "return false;\n"
                + "}\n"
                + "checker%d |= (1L << val);\n"
                + "break;\n", i, i, i));
    }
    sb.append("}\n"
            + "}\n"
            + "return true;");
    System.out.println(sb);
}

Answer 2

Sólo se necesita una línea de...menos de una línea en realidad:

if (str.matches("((.)(?!.*\\1))*"))

este utiliza un negativo mirar hacia adelante para afirmar que cada personaje no se repite más adelante en la cadena.

Este enfoque de un tiempo la complejidad de O(n^2), porque para todos los n caracteres en la entrada, todos los caracteres que siguen (hay n de los) se comparan para la igualdad.

Answer 3

Creo que necesitamos un general y definición práctica de "otras estructuras de datos".Intuitivamente, no queremos llamar a todos los escalares entero o puntero de una "estructura de datos", ya que hace tonterías de toda prohibición de "otras estructuras de datos".

Propongo que pedir prestado un concepto de big-O notación:una "estructura de datos adicionales" es uno que crece con el tamaño del conjunto de datos.

En el presente caso, el código citado por el OP parece haber una necesidad de espacio de O(1) debido a que el bit vector sucede para que se ajuste a un tipo entero.Pero como el OP implica, la forma general de que el problema realmente es O(N).

Un ejemplo de una solución para el caso general es el uso de dos punteros y un bucle anidado simplemente comparar cada carácter a todos los otros.El requerimiento de espacio es O(1), pero el requisito de tiempo es O(N^2).

Answer 4

Cómo sobre el siguiente algoritmo?

Pasos:

Convertir la cadena a minúsculas.

El bucle a través de cada carácter en la cadena

Conjunto de datos de la variable = 0

Calcular el offset = valor ascii del primer carácter en la cadena - 97

Establecer el indicador para esa posición con la máscara = 1 << offset

Si el bit a bit Y devuelve true, entonces es un personaje de repetición (máscara y datos), por lo que romper aquí.

si por el contrario, no hemos visto la repetición de caracteres sin embargo, establezca el bit de ese personaje haciendo un bit a bit O haciendo de datos = datos | máscara

Continuar hasta el final de los personajes.