Buscar..


Introducción

Dos cadenas con el mismo conjunto de caracteres se llaman anagramas. He utilizado javascript aquí.

Crearemos un hash de str1 y aumentaremos la cuenta +1. Haremos un bucle en la segunda cadena y comprobaremos que todos los caracteres están en hash y disminuiremos el valor de la clave hash. Compruebe que todo el valor de la clave hash es cero será anagrama.

Muestra de entrada y salida

Ex1: -

let str1 = 'stackoverflow';
let str2 = 'flowerovstack';

Estas cuerdas son anagramas.

// Crear Hash desde str1 y aumentar una cuenta.

hashMap = {
    s : 1,
    t : 1,
    a : 1,
    c : 1,
    k : 1,
    o : 2,
    v : 1,
    e : 1,
    r : 1,
    f : 1,
    l : 1,
    w : 1
}

Puede ver que la hashKey 'o' contiene el valor 2 porque o es 2 veces en una cadena.

Ahora pase sobre str2 y verifique que cada carácter esté presente en hashMap, si es así, reduzca el valor de la clave hashMap, de lo contrario, devuelva false (lo que indica que no es un anagrama).

hashMap = {
    s : 0,
    t : 0,
    a : 0,
    c : 0,
    k : 0,
    o : 0,
    v : 0,
    e : 0,
    r : 0,
    f : 0,
    l : 0,
    w : 0
}

Ahora, haga un bucle sobre el objeto hashMap y verifique que todos los valores sean cero en la clave de hashMap.

En nuestro caso, todos los valores son cero, por lo que es un anagrama.

Código genérico para anagramas

(function(){

    var hashMap = {};
    
    function isAnagram (str1, str2) {
    
        if(str1.length !== str2.length){
            return false;
        }
        
        // Create hash map of str1 character and increase value one (+1).
        createStr1HashMap(str1);

        // Check str2 character are key in hash map and decrease value by one(-1);
        var valueExist = createStr2HashMap(str2);

        // Check all value of hashMap keys are zero, so it will be anagram.
        return isStringsAnagram(valueExist);
    }
    
    function createStr1HashMap (str1) {
        [].map.call(str1, function(value, index, array){
            hashMap[value] = value in hashMap ?  (hashMap[value] + 1) : 1;
            return value;
        });
    }
    
    function createStr2HashMap (str2) {
        var valueExist = [].every.call(str2, function(value, index, array){
            if(value in hashMap) {
                hashMap[value] = hashMap[value] - 1;
            }
            return value in hashMap;
        });
        return valueExist;
    }
    
    function isStringsAnagram (valueExist) {
        if(!valueExist) {
            return valueExist;
        } else {
            var isAnagram;
            for(var i in hashMap) {
                if(hashMap[i] !== 0) {
                    isAnagram = false;
                    break;
                } else {
                    isAnagram = true;
                }
            }
    
            return isAnagram;
        }
    }
    
    isAnagram('stackoverflow', 'flowerovstack'); // true
    isAnagram('stackoverflow', 'flowervvstack'); // false
    
})();

Complejidad del tiempo: - 3n es decir O (n).



Modified text is an extract of the original Stack Overflow Documentation
Licenciado bajo CC BY-SA 3.0
No afiliado a Stack Overflow