Действительная анаграмма – LeetCode
Действительная анаграмма – при наличии двух строк s и t вернуть true, если t является анаграммой s, и false в противном случае. Анаграмма — это…leetcode.com



С каждым отдельным символом String s мы можем создать String t.

Если мы проанализируем слово 'Anagram', то обнаружим, что это слово состоит из 'aaa'(3) 'n'(1) 'g'(1) 'r'(1) 'm '(1) → 7 символов

Первое решение

Если мы используем Hashmap(key, value) , мы можем сохранить букву для ключа и номер ключа для значения, и мы можем проверить, равны ли эти две строки или нет.

public class Solution_HashMap {
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> s1 = new HashMap<>();
        Map<Character, Integer> t1 = new HashMap<>();
        if(s.length() != t.length()) return false;
        for(int i = 0; i < s.length(); i++) {
            s1.put(s.charAt(i),s1.getOrDefault(s.charAt(i),0)+1);
            t1.put(t.charAt(i),t1.getOrDefault(t.charAt(i),0)+1);
        }
        return s1.equals(t1);
    }
}
//Runtime: 19 ms, faster than 18.80% of Java online submissions for Valid Anagram.
//Memory Usage: 42.9 MB, less than 38.54% of Java online submissions for Valid Anagram.

//from : https://leetcode.com/problems/valid-anagram/solutions/233567/java-solution-using-hashmap/

Но если мы создадим два таких хэш-карты, временная сложность и сложность памяти будут слишком большими. Как мы видим, этот метод быстрее только 18,80% заявок на leetcode. Итак, как мы можем решить эту проблему?

Окончательное решение

Вместо этого мы используем Hashmap. Мы можем просто отсортировать эти две строки вот так и проверить, верны эти строки или нет!

public class Solution_Sort {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        Arrays.sort(sArr);
        Arrays.sort(tArr);
        for(int i = 0; i<sArr.length; i++) {
            if(sArr[i] != tArr[i]) return false;
        }
        return true;
    }
}
//Time: O(nlogn)
//Space: O(1)

//Runtime: 3 ms, faster than 82.74% of Java online submissions for Valid Anagram.
//Memory Usage: 42.6 MB, less than 53.14% of Java online submissions for Valid Anagram.

//from : https://leetcode.com/problems/valid-anagram/solutions/471783/java-hashmap-sort-explanations

Таким образом, этот метод становится быстрее, чем 82,74% заявок на leetcode.

Ресурсы:



Решение Java с использованием HashMap — Valid Anagram — LeetCode
Просмотрите решение nkkbr для Valid Anagram на LeetCode, крупнейшем в мире сообществе программистов.leetcode.com



https://leetcode.com/problems/valid-anagram/solutions/471783/java-hashmap-sort-explanations/