首页 > itarticle > algorithm notes: leetcode#242 valid anagram

algorithm notes: leetcode#242 valid anagram

admin 11月 12, 2020 0

Problem

Solution

Analysis

Python implementation

class :
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        counter = dict()
        for c in s:
            counter[c] = counter.get(c, 0) + 1
        for c in t:
            if not counter.get(c, 0):
                return False
            counter[c] -= 1
        return sum(counter.values()) == 0

Java implementation

class  {
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> counter = new HashMap<>();
        for(char c : s.toCharArray()){
            counter.put(c, counter.getOrDefault(c, 0)+1);
        }
        for(char c : t.toCharArray()){
            int freq = counter.getOrDefault(c, 0);
            if(freq==0){ return false; }
            counter.put(c, freq-1);
        }
        int sum = 0;
        for(int f : counter.values()){
            sum += f;
        }
        return sum==0;
    }
}

Time complexity

O(n).

Space complexity

O(1).

Link

242. Valid Anagram
(中文版) 算法笔记: 力扣#242 有效的字母异位词