java - for - big o rapper

Detectando si una cadena tiene caracteres únicos: comparando mi solución con "Cracking the Coding Interview?"

Question

Estoy trabajando en el libro "Cracking the Coding Interview" (Entrechoque de la entrevista de codificación) y me he encontrado con preguntas que me piden respuestas, pero necesito ayuda para comparar mi respuesta con la solución. Mi algoritmo funciona, pero estoy teniendo dificultades para entender la solución en el libro. Principalmente porque no entiendo lo que algunos de los operadores realmente están haciendo.

La tarea es: "Implementar un algoritmo para determinar si una cadena tiene todos los caracteres únicos. ¿Qué pasa si no puede usar estructuras de datos adicionales?"

Esta es mi solución:

public static boolean checkForUnique(String str){
    boolean containsUnique = false;

    for(char c : str.toCharArray()){
        if(str.indexOf(c) == str.lastIndexOf(c)){
            containsUnique = true;
        } else {
            containsUnique = false;
        }
    }

    return containsUnique;
}

Funciona, pero ¿qué tan eficiente es esto? Vi que la complejidad de las funciones de índice para String en Java es O (n * m)

Aquí está la solución del libro:

public static boolean isUniqueChars(String str) {
    if (str.length() > 256) {
        return false;
    }
    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;
}

Un par de cosas que no entiendo muy bien con la solución. Primero, ¿qué hace el operador "| ="? ¿Por qué se resta ''a'' del carácter actual en la cadena para el valor de "val"? Sé que "<<" es un cambio a la izquierda en modo bit, pero ¿qué hace (checker & (1<<val)) ? Sé que es a nivel de bit y, pero no lo entiendo, ya que no estoy entendiendo la línea en la que el verificador obtiene un valor.

Simplemente no estoy familiarizado con estas operaciones y, lamentablemente, el libro no da una explicación de las soluciones, probablemente porque asume que ya comprende estas operaciones.

Answer 1

Actualización de la 6ª edición

    public static void main(String[] args) {
        System.out.println(isUniqueChars("abcdmc")); // false
        System.out.println(isUniqueChars("abcdm")); // true
        System.out.println(isUniqueChars("abcdm/u0061")); // false because /u0061 is unicode a
    }


    public static boolean isUniqueChars(String str) {
        /*
         You should first ask your interviewer if the string is an ASCII string or a Unicode string.
         Asking this question will show an eye for detail and a solid foundation in computer science.
         We''ll assume for simplicity the character set is ASCII.
         If this assumption is not valid, we would need to increase the storage size.
         */
        // at 6th edition of the book, there is no pre condition on string''s length
        /*
         We can reduce our space usage by a factor of eight by using a bit vector.
         We will assume, in the below code, that the string only uses the lowercase letters a through z.
         This will allow us to use just a single int.
          */
        // printing header to provide nice csv format log, you may uncomment
//        System.out.println("char,val,valBinaryString,leftShift,leftShiftBinaryString,checker");
        int checker = 0;
        for (int i = 0; i < str.length(); i++) {
            /*
                Dec Binary Character
                97  01100001    a
                98  01100010    b
                99  01100011    c
                100 01100100    d
                101 01100101    e
                102 01100110    f
                103 01100111    g
                104 01101000    h
                105 01101001    i
                106 01101010    j
                107 01101011    k
                108 01101100    l
                109 01101101    m
                110 01101110    n
                111 01101111    o
                112 01110000    p
                113 01110001    q
                114 01110010    r
                115 01110011    s
                116 01110100    t
                117 01110101    u
                118 01110110    v
                119 01110111    w
                120 01111000    x
                121 01111001    y
                122 01111010    z
             */
            // a = 97 as you can see in ASCII table above
            // set val to be the difference between the char at i and ''a''
            // b = 1, d = 3.. z = 25
            char c = str.charAt(i);
            int val = c - ''a'';
            // means "shift 1 val numbers places to the left"
            // for example; if str.charAt(i) is "m", which is the 13th letter, 109 (g in ASCII) minus 97 equals 12
            // it returns 1 and 12 zeros = 1000000000000 (which is also the number 4096)
            int leftShift = 1 << val;
            /*
                An integer is represented as a sequence of bits in memory.
                For interaction with humans, the computer has to display it as decimal digits, but all the calculations
                are carried out as binary.
                123 in decimal is stored as 1111011 in memory.

                The & operator is a bitwise "And".
                The result is the bits that are turned on in both numbers.

                1001 & 1100 = 1000, since only the first bit is turned on in both.

                It will be nicer to look like this

                1001 &
                1100
                =
                1000

                Note that ones only appear in a place when both arguments have a one in that place.

             */
            int bitWiseAND = checker & leftShift;
            String leftShiftBinaryString = Integer.toBinaryString(leftShift);
            String checkerBinaryString = leftPad(Integer.toBinaryString(checker), leftShiftBinaryString.length());
            String leftShiftBinaryStringWithPad = leftPad(leftShiftBinaryString, checkerBinaryString.length());
//            System.out.printf("%s &/n%s/n=/n%s/n/n", checkerBinaryString, leftShiftBinaryStringWithPad, Integer.toBinaryString(bitWiseAND));
            /*
            in our example with string "abcdmc"
            0 &
            1
            =
            0

            01 &
            10
            =
            0

            011 &
            100
            =
            0

            0111 &
            1000
            =
            0

            0000000001111 &
            1000000000000
            =
            0

            1000000001111 &
            0000000000100
            =
            100
             */
//            System.out.println(c + "," + val + "," + Integer.toBinaryString(val) + "," + leftShift + "," + Integer.toBinaryString(leftShift) + "," + checker);
            /*
            char val valBinaryString leftShift leftShiftBinaryString checker
            a   0       0               1       1                       0
            b   1       1               2       10                      1
            c   2       10              4       100                     3
            d   3       11              8       1000                    7
            m   12      1100            4096    1000000000000           15
            c   2       10              4       100                     4111
             */
            if (bitWiseAND > 0) {
                return false;
            }
            // setting 1 on on the left shift
            /*
            0000000001111 |
            1000000000000
            =
            1000000001111
             */
            checker = checker | leftShift;
        }
        return true;
        /*
        If we can''t use additional data structures, we can do the following:
        1. Compare every character of the string to every other character of the string.
            This will take 0( n 2 ) time and 0(1) space
        2. If we are allowed to modify the input string, we could sort the string in O(n log(n)) time and then linearly
            check the string for neighboring characters that are identical.
            Careful, though: many sorting algorithms take up extra space.

        These solutions are not as optimal in some respects, but might be better depending on the constraints of the problem.
         */
    }

    private static String leftPad(String s, int i) {
        StringBuilder sb = new StringBuilder(s);
        int charsToGo = i - sb.length();
        while (charsToGo > 0) {
            sb.insert(0, ''0'');
            charsToGo--;
        }
        return sb.toString();
    }

Answer 2

Aquí hay dos preguntas separadas: ¿cuál es la eficiencia de su solución y qué hace la solución de referencia? Vamos a tratar a cada uno de forma independiente.

Primero, tu solución:

public static boolean checkForUnique(String str){
    boolean containsUnique = false;

    for(char c : str.toCharArray()){
        if(str.indexOf(c) == str.lastIndexOf(c)){
            containsUnique = true;
        } else {
            containsUnique = false;
        }
    }

    return containsUnique;
}

Su solución consiste esencialmente en un bucle sobre todos los caracteres de la cadena (digamos que hay n de ellos), verificando en cada iteración si el primer y último índice de los caracteres son iguales. Los métodos indexOf y lastIndexOf llevan tiempo O (n), porque tienen que explorar todos los caracteres de la cadena para determinar si alguno de ellos coincide con el que está buscando. Por lo tanto, dado que su ciclo ejecuta O (n) veces y O (n) funciona por iteración, su tiempo de ejecución es O (n ² ).

Sin embargo, hay algo dudoso sobre tu código. Intente ejecutarlo en la cadena aab . ¿Funciona correctamente en esta entrada? Como sugerencia, tan pronto como determine que hay dos o más caracteres duplicados, tendrá la garantía de que hay duplicados y podrá devolver que no todos los caracteres son únicos.

Ahora, veamos la referencia:

public static boolean isUniqueChars(String str) {
    if (str.length() > 256) { // NOTE: Are you sure this isn''t 26?
        return false;
    }
    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;
}

Esta solución es linda. La idea básica es la siguiente: imagina que tienes una matriz de 26 booleanos, cada uno rastreando si un personaje en particular ya apareció en la cadena. Comienzas con todos ellos falsos. A continuación, itera a través de los caracteres de la cadena, y cada vez que ve un personaje mira en la ranura de la matriz para ese personaje. Si es false , esta es la primera vez que ves al personaje y puedes establecerlo en true . Si es true , ya has visto este personaje y puedes informar inmediatamente que hay un duplicado.

Tenga en cuenta que este método no asigna una matriz de booleanos. En cambio, opta por un truco ingenioso. Como solo hay 26 caracteres diferentes posibles y hay 32 bits en un int , la solución crea una variable int donde cada bit de la variable corresponde a uno de los caracteres de la cadena. En lugar de leer y escribir una matriz, la solución lee y escribe los bits del número.

Por ejemplo, mira esta línea:

if ((checker & (1 << val)) > 0) return false;

¿Qué hace checker & (1 << val) ? Bueno, 1 << val crea un valor int que tiene todos los bits cero, excepto el val th bit. Luego usa AND a nivel de bit AND con este valor con checker . Si el bit en la posición val en el checker ya está configurado, entonces se evalúa con un valor distinto de cero (lo que significa que ya hemos visto el número) y podemos devolver falso. De lo contrario, se evalúa a 0 y no hemos visto el número.

La siguiente línea es esta:

checker |= (1 << val);

Utiliza el operador "bitwise OR with assignment", que es equivalente a

checker = checker | (1 << val);

Este checker OR con un valor que tiene un bit de 1 solo en la posición val , que enciende la bit. Es equivalente a establecer el val th bit del número en 1.

Este enfoque es mucho más rápido que el tuyo. Primero, dado que la función comienza verificando si la cadena tiene una longitud mayor a 26 (supongo que el 256 es un error tipográfico), la función nunca tiene que probar ninguna cadena de longitud 27 o superior. Por lo tanto, el ciclo interno funciona como máximo 26 veces. Cada iteración funciona O (1) en operaciones bit a bit, por lo que el trabajo total realizado es O (1) (O (1) iteraciones por O (1) trabajo por iteración), que es significativamente más rápido que su implementación.

Si no ha visto operaciones bit a bit utilizadas de esta manera, le recomendaría buscar "operadores bit a bit" en Google para obtener más información.

¡Espero que esto ayude!

Answer 3

Como se hace referencia a ''Cracking the Coding Interview'', existe una solución alternativa:

boolean isUniqueChars(String str) {
  if(str.length() > 128) return false;

  boolean[] char_set = new boolean[128];
  for(int i = 0; i < str.length(); i++) {
    int val = str.charAt(i);

    if(char_set[val]) {
      return false;
    }
    char_set[val] = true;
  }
  return true;
}

Por supuesto, para lograr una mejor complejidad del espacio, consulte el ejemplo anterior por @templatetypedef

Answer 4

Como un valor de char puede contener uno de solo 256 valores diferentes, cualquier cadena que tenga más de 256 caracteres debe contener al menos un duplicado.

El resto del código usa el checker como una secuencia de bits, donde cada bit representa un carácter. Parece convertir cada carácter en un entero, comenzando con a = 1. Luego verifica el bit correspondiente en el checker . Si está configurado, significa que el carácter ya se ha visto y, por lo tanto, sabemos que la cadena contiene al menos un carácter duplicado. Si el carácter aún no se ha visto, el código establece el bit correspondiente en el checker y continúa.

Específicamente, (1<<val) genera un número entero con un solo 1 bit en la posición val . Por ejemplo, (1<<3) sería 1000 binario o 8. El checker & (1<<val) expresión checker & (1<<val) devolverá cero si el bit en posición val no está establecido (es decir, tiene valor 0) en el checker , y (1<<val) , que siempre es distinto de cero, si ese bit está configurado. El checker |= (1<<val) expresiones checker |= (1<<val) configurará ese bit en el checker .

Sin embargo, el algoritmo parece ser defectuoso: no parece dar cuenta de los caracteres en mayúscula y la puntuación (que generalmente aparecen antes que las minúsculas lexicográficamente). También parece requerir un entero de 256 bits, que no es estándar.

Como menciona en el comentario a continuación, prefiero su solución porque funciona. Puedes optimizarlo devolviendo false tan pronto como identifiques un personaje no único.

Answer 5

Esta es la corrección necesaria para el código del libro:

public static boolean checkForUnique(String str){
    boolean containsUnique = false;

    for(char c : str.toCharArray()){
        if(str.indexOf(c) == str.lastIndexOf(c)){
            containsUnique = true;
        } else {
            return false;
        }
    }

    return containsUnique;
}

Answer 6

La solución de libros es una que no me gusta y creo que es disfuncional ..... templatetypedef ha publicado una respuesta completa que indica que la solución es buena. No estoy de acuerdo, ya que la respuesta del libro asume que la cadena solo tiene caracteres en minúscula (ascii) y no tiene validez para garantizarlo.

public static boolean isUniqueChars(String str) {
    // short circuit - supposed to imply that
    // there are no more than 256 different characters.
    // this is broken, because in Java, char''s are Unicode,
    // and 2-byte values so there are 32768 values
    // (or so - technically not all 32768 are valid chars)
    if (str.length() > 256) {
        return false;
    }
    // checker is used as a bitmap to indicate which characters
    // have been seen already
    int checker = 0;
    for (int i = 0; i < str.length(); i++) {
        // set val to be the difference between the char at i and ''a''
        // unicode ''a'' is 97
        // if you have an upper-case letter e.g. ''A'' you will get a
        // negative ''val'' which is illegal
        int val = str.charAt(i) - ''a'';
        // if this lowercase letter has been seen before, then
        // the corresponding bit in checker will have been set and
        // we can exit immediately.
        if ((checker & (1 << val)) > 0) return false;
        // set the bit to indicate we have now seen the letter.
        checker |= (1 << val);
    }
    // none of the characters has been seen more than once.
    return true;
}

El resultado final, dada la respuesta de templatedef también, es que en realidad no hay suficiente información para determinar si la respuesta del libro es correcta.

Sin embargo, desconfío.

La respuesta de templatedef sobre la complejidad es una con la que estoy de acuerdo ... ;-)

EDITAR: Como ejercicio, convertí la respuesta del libro a una que funcionará (aunque sea más lenta que la respuesta del libro: BigInteger es lento) .... Esta versión tiene la misma lógica que la del libro, pero no tiene la misma validación y problemas de asunción (pero es más lento). También es útil mostrar la lógica.

public static boolean isUniqueChars(String str) {
    if (str.length() > 32768) {
        return false;
    }
    BigInteger checker = new BigInteger(0);
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i);
        if (checker.testBit(val)) return false;
        checker = checker.setBit(val);
    }
    // none of the characters has been seen more than once.
    return true;
}

Answer 7

La solución del libro no distingue entre mayúsculas y minúsculas. ''A'' y ''a'' se consideran duplicados según la implementación.

Explicación: para la cadena de entrada con char ''A'', ''A'' - ''a'' es -32 por lo que ''1 << val'' se evaluará como 1 << -32. desplazar en cualquier número negativo desplazará los bits en dirección opuesta. por lo tanto 1 << -32 será 1 >> 32. Que establecerá el primer bit en 1. Este es también el caso con char ''a''. Por lo tanto, ''A'' y ''a'' se consideran caracteres duplicados. Del mismo modo para ''B'' y ''b'', el segundo bit se establece en 1 y así sucesivamente.