242. 有效的字母异位词

发表评论
363 views

 ›
242. 有效的字母异位词

官方链接

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

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

思路

  1. 暴力 sort sorted_str 相等？ O(nlogn)
  2. hash map 统计每个字符的频次

解法一

先排序 再比较

排序用快排的话 是 O(NlogN)

class Solution {
    public boolean isAnagram(String s, String t) {

        if (s.length() != t.length()) return false;
        char[] s1 = s.toCharArray();
        char[] t1 = t.toCharArray();

        Arrays.sort(s1);
        Arrays.sort(t1);

        for (int i = 0; i < s1.length; i++) {
            if (s1[i] != t1[i]) return false;
        }
        return true;
    }
}

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

解法二

利用 哈希表 统计词频

func isAnagram(s string, t string) bool {

  if len(s) != len(t) {
    return false
  }

  smap := make(map[int]int)
  tmap := make(map[int]int)
  for i:=0; i < len(s); i++ {
    smap[int(s[i] - 'a')] += 1 
    tmap[int(t[i] - 'a')] += 1 
  }

  for k,v := range smap {
    if tmap[k] != v {
      return false
    }
  }
  return true
}

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        dic1, dic2 = [0]*26, [0]*26
        for item in s:
            dic1[ord(item) - ord('a')] += 1
        for item in t:
            dic2[ord(item) - ord('a')] += 1
        return dic1 == dic2

解法三

用 counter 遍历第一个字符串，记录字符出现次数。第二次遍历对应减少 counter 字符的值。
如果减为负，则说明不是异位词

class Solution {
    public boolean isAnagram(String s, String t) {

        if (s.length() != t.length()) return false;

        Map<Character, Integer> m = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (m.containsKey(c)) m.put(c, m.get(c) + 1);
            else m.put(c, 1);
        }

        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            int count = m.getOrDefault(c, 0);
            count--;

            if (count < 0) return false;

            m.put(c, m.get(c) - 1);
        }
        return true;
    }
}