Check Permutacion

Si te pido que hagas un metodo que me averigue si dos strings son permutaciones la una de la otra, como lo harías?

Piensa en qué significa que un String sea una permutación de la otra? Por ejemplo “ABC” es una permutacion de "CBA”, pero “XBA” no lo es - ya que no puedes cambiar las letras de “ABC” para obtener “XBA”.

👉 Link aquí hacia el repo para solucionar el problema

👌 Tips

Hay una solución que es en O(N Log N) y hay otra que es en O(N)

Dos Permutaciones tienen la misma longitud pero en diferente orden, haría alguna diferencia ordenarlos?

Has Pensado en usar un HashTable?

👊 Solución 1

Si podemos ordenar ambas Strings y despues compararlas. Esto nos tomaría un tiempo estimado de O(N Log N + M Log M), que es el tiempo que requiere ordenar ambas Strings.

Vale la pena tomar en cuenta que aunque este algoritmo no sea el más eficiente, puede ser mas preferible en otro sentido. Ya que es muy limpio, simple y fácil de entender.

public boolean sortingSolution(String s1, String s2) {
    int s1L = s1.length();
    int s2L = s2.length();
    if (s1L != s2L) return false;
    String s1Sorted = sortString(s1); // O(s1 log s1)
    String s2Sorted = sortString(s2); // O(s2 log s2)
    return s1Sorted.equals(s2Sorted);
}

static String sortString(String string) {
    char temp[] = string.toCharArray();
    Arrays.sort(temp);
    return new String(temp);
}

👊 Solución 2

Con un HashMap podríamos obetner una solución es mas eficiente - O(N), siendo N la longitud de una de las Strings.

Esta solución es un poco mas complicada de entender y bastante más verbosa. Lo que hacemos es iterar sobre ambas Strings una vez (dado que sabemos que tienen la misma longitud) y para la primera String agregamos un +1 en ese carácter, y para la segunda string hacemos un -1. Al final sumamos todos los valores que nos quedan y cualquier numero diferente a 0 sabremos que tienen diferente cuentas de caracteres.

public boolean hashMapSolution(String s1, String s2) {
    int s1L = s1.length();
    int s2L = s2.length();
    if (s1L != s2L) return false;

    char[] s1Chars = s1.toCharArray();
    char[] s2Chars = s2.toCharArray();
    Map<Character, Integer> checker = new HashMap<>();

    for (int I = 0; I < s1L; I++) {
        char c1 = s1Chars[I];
        char c2 = s2Chars[I];
        insertCharToHashMap(checker, c1, 1);
        insertCharToHashMap(checker, c2, -1);
    }

    int sum = checker.values().stream().reduce(0, Integer::sum);
    return sum == 0;
}

void insertCharToHashMap(Map<Character, Integer> hashMap, char c, int value) {
    if (hashMap.containsKey(c)) {
        int newVal = hashMap.get(c) + value;
        hashMap.put(c, newVal);
    } else {
        hashMap.put(c, value);
    }
}

👊 Solución 3

Con un Array y asumiendo que nuestra solucion se encuentra dentro del diccionario ASCII podríamos tener otra solución que se escribe mas simple y limpiamente y también en O(N).

Utilizamos un Array con 128 espacios. Iteramos sobre String 1 primero añadiendo +1 por cada carácter que encontramos en el espacio correcto del Array. Después iteramos sobre String 2 y si algún carácter reduce abajo de 0 significa que hay diferentes caracteres en el Segundo String y no es una permutación.

public boolean arraySolution(String s1, String s2) {
    int s1L = s1.length();
    int s2L = s2.length();
    if (s1L != s2L) return false;
    int[] checker = new int[128];

    char[] s1Chars = s1.toCharArray();
    char[] s2Chars = s2.toCharArray();
    // we know that ASCII chars are from 0 to 127
    for (char s1Char : s1Chars) {
        checker[s1Char]++;
    }

    for (char s2Char : s2Chars) {
        checker[s2Char]—;
        if (checker[s2Char] < 0) return false;
    }
    return true;
}

Siempre recuerda de preguntar si solamente estas utilizando los caracteres del set ASCII

---

Pregunta prestada del libro "Cracking the coding interview”