Поиск…


Вступление

Две строки с одинаковым набором символов называются анаграммами. Я использовал javascript здесь.

Мы создадим хэш str1 и увеличим счет +1. Мы будем зацикливаться на 2-й строке и проверять наличие всех символов в хэше и уменьшить значение хэш-ключа. Проверьте, что все значение хэш-клавиши равно нулю, будет анаграммой.

Пример ввода и вывода

Ex1: -

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

Эти строки являются анаграммами.

// Создаем хэш из str1 и увеличиваем один счетчик.

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
}

Вы можете видеть, что hashKey 'o' содержит значение 2, потому что o 2 раза в строке.

Теперь loop over str2 и проверка каждого символа присутствуют в hashMap, если да, уменьшите значение hashMap Key, иначе верните false (что указывает, что это не анаграмма).

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
}

Теперь перетащите объект hashMap и проверьте, что все значения равны нулю в ключе hashMap.

В нашем случае все значения равны нулю, поэтому его анаграмма.

Общий код для анаграмм

(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
    
})();

Сложность времени: - 3n, т.е. O (n).



Modified text is an extract of the original Stack Overflow Documentation
Лицензировано согласно CC BY-SA 3.0
Не связан с Stack Overflow