Действительная анаграмма. (Серия Javascript DSA)

Содержание

Проблема
Решение
Способ первый
Способ второй

Проблема

Задав две строки s и t, вернуть true, если t является анаграммой s, и false в противном случае.

Анаграмма — это слово или фраза, образованная путем перестановки букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.

Пример
Вход: s = «anagram», t = «nagaram».
Выход: истина
Вход: s = «крыса», t = «машина»
Выход: false
Ограничения
1 <= s.length, t.length <= 5 * 104
s и t состоят из строчных английских букв.

Решение

Существует два способа решения этой задачи.

Способ первый

/**
 * Since t is compared to s,
 * convert all to lowercase,
 * sort t and s, 
 * if t is exactly equal to s, then it is an anagram, else it isn't
 * Runtime O(n)
 */

// const s = "anagram";
// const t = "nagaram" 
const s = "rat", t = "car"
function anagram(s, t){
    const sortedS = s.split('').sort().join('');
    const sortedT = t.split('').sort().join('');
    if (sortedS === sortedT) return true;
    return false;
}

Войдите в полноэкранный режим Выйти из полноэкранного режима

Способ второй

Использование карты

/**
 * Create a map object
 * For each char in S, add the first occurrence with a value of 1. For subsequent occurrence, increase the value by +1.
 * For each char in T, if it doesn't exist in map i.e undefined or value is <= 0, return false. If it does exist, do value -1, return true outside loop.
 * @param {*} s 
 * @param {*} t 
 */

function anagramTwo(s,t){
    // for our answer to be an anagram, the word must be rearranged, hence, if the length of the two words are not same, it is not an anagram.
    if(s.length !== t.length) return false;

    const map = {};
    for (let i of s) {
        if(map[i] !== undefined) {
            map[i]++
         } else map[i] = 1
    }

    for (let i of t){
        if (map[i] === undefined || map[i] <= 0) return false;
        map[i]--;
    }
    return true

}

console.log(anagramTwo("ab", "a"))