0242._valid_anagram.md

Navigation

• Navigation
• Links
• Solution 1 collections.Counter
• Solution 2 排序
• Solution 3 哈希表

Links

1. https://leetcode.com/problems/valid-anagram/
2. https://leetcode-cn.com/problems/valid-anagram/

Solution 1 collections.Counter

import collections


class Solution:
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        return collections.Counter(s) == collections.Counter(t)

Solution 2 排序

    因为是timsort
    时间复杂度：O(nlogn)
    空间复杂度：O(n)

class Solution:
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        return sorted(s) == sorted(t)

---

Go

func isAnagram(s, t string) bool {
	s1, s2 := []byte(s), []byte(t)
	sort.Slice(s1, func(i, j int) bool { return s1[i] < s1[j] })
	sort.Slice(s2, func(i, j int) bool { return s2[i] < s2[j] })
	return string(s1) == string(s2)
}

Solution 3 哈希表

用dict做计数器。如果在任何时候计数器低于零，就提前退出。

    时间复杂度：O(n)
    空间复杂度：O(n)

class Solution:
    def isAnagram(self, s, t):
        if len(s) != len(t):
            return False

        hash_table = {}

        for char in s:
            hash_table[char] = hash_table.get(char, 0) + 1
        
        for char in t:
            hash_table[char] = hash_table.get(char, 0) - 1
            
            if hash_table[char] < 0:    # 提前退出
                return False

        return True

---

Go

func isAnagram(s, t string) bool {
	if len(s) != len(t) {
		return false
	}

	m := make(map[rune]int)

	for _, ch := range s {
		m[ch]++
	}

	for _, ch := range t {
		m[ch]--

		if m[ch] < 0 {
			return false
		}
	}

	return true
}