Решение: Допустимая Анаграмма

Это часть серии пояснений к решению Leetcode ( index ). Если вам понравилось это решение или вы нашли его полезным, пожалуйста, поставьте лайк этому сообщению и/или поддержите/ | сообщение о моем решении на форумах Leetcode/| .

Проблема с Leetcode #242 (Простая): Допустимая анаграмма

Описание:

Даны две строки s и t , напишите функцию , чтобы определить, является ли t является анаграммой s .

Примеры:

Ввод:
Выход:	истинный

Ввод:
Выход:	ложный

Ограничения:

Вы можете предположить, что строка содержит только строчные буквы.

Идея:

Анаграмма слова – это, по сути, другое слово, в котором используются те же буквы с той же частотой, только в другом порядке. Поскольку мы заботимся только о буквах и их частоте, самый простой выбор – использовать частотную карту .

Поскольку мы имеем дело со строчными буквами, мы можем повысить производительность, используя массив вместо более традиционной карты и преобразуя символы в их номер в юникоде ( 97 – 122 ) для хранения.

Сначала мы перебираем первую строку S и увеличиваем каждую позицию кода символа в нашей частотной карте ( fmap ). Затем мы проходим через вторую строку T и уменьшите позиции символьного кода в fmap . Если мы когда-нибудь опустимся ниже 0 тогда мы знаем, что у нас есть частота символов в T это не то же самое, что S , поэтому мы должны вернуть false .

Однако, если мы доберемся до конца без проблем, мы должны вернуть true .

Реализация:

В javascript мы можем использовать типизированный массив Int16Array , чтобы сделать процесс еще более производительным.

В Python есть строковая функция count() , которая делает эту проблему еще быстрее.

Код Javascript:

var isAnagram = function(S, T) {
    let len = S.length, fMap = new Int16Array(123)
    if (T.length !== len) return false
    for (let i = 0; i < len; i++)
        fMap[S.charCodeAt(i)]++
    for (let i = 0; i < len; i++)
        if (--fMap[T.charCodeAt(i)] < 0) return false
    return true
};

Код на Python:

class Solution:
    def isAnagram(self, S: str, T: str) -> bool:
        SMap = {c: S.count(c) for c in set(S)}
        TMap = {c: T.count(c) for c in set(T)}
        return SMap == TMap

Java-код:

class Solution {
    public boolean isAnagram(String S, String T) {
        int len = S.length();
        int[] fMap = new int[123];
        if (T.length() != len) return false;
        for (int i = 0; i < len; i++)
            fMap[S.codePointAt(i)]++;
        for (int i = 0; i < len; i++)
            if (--fMap[T.codePointAt(i)] < 0) return false;
        return true;
    }
}

Код на C++:

class Solution {
public:
    bool isAnagram(string S, string T) {
        int len = S.length();
        int fMap [123] = {0};
        if (T.length() != len) return false;
        for (int i = 0; i < len; i++)
            fMap[int(S[i])]++;
        for (int i = 0; i < len; i++)
            if (fMap[int(T[i])]-- == 0) return false;
        return true;
    }
};

Оригинал: “https://dev.to/seanpgallivan/solution-valid-anagram-3l06”

Проблема с Leetcode #242 (Простая): Допустимая анаграмма

Читайте ещё по теме: