Question

242. 有效的字母异位词

English Version

题目描述

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

注意：若 _s_ 和 _t__ _中每个字符出现的次数都相同，则称 _s_ 和 _t__ _互为字母异位词。

 

示例 1:

输入: _s_ = "anagram", _t_ = "nagaram"
输出: true

示例 2:

输入: _s_ = "rat", _t_ = "car"
输出: false

 

提示:

• 1 <= s.length, t.length <= 5 * 104
• s 和 t 仅包含小写字母

 

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

解法

方法一：计数

我们先判断两个字符串的长度是否相等，如果不相等，说明两个字符串中的字符肯定不同，返回 false。

否则，我们用哈希表或者一个长度为 $26$ 的数组来记录字符串 $s$ 中每个字符出现的次数，然后遍历另一个字符串 $t$，每遍历到一个字符，就将哈希表中对应的字符次数减一，如果减一后的次数小于 $0$，说明该字符在两个字符串中出现的次数不同，返回 false。如果遍历完两个字符串后，哈希表中的所有字符次数都为 $0$，说明两个字符串中的字符出现次数相同，返回 true。

时间复杂度 $O(n)$，空间复杂度 $O(C)$，其中 $n$ 是字符串的长度；而 $C$ 是字符集的大小，本题中 $C=26$。

class Solution:
  def isAnagram(self, s: str, t: str) -> bool:
    if len(s) != len(t):
      return False
    cnt = Counter(s)
    for c in t:
      cnt[c] -= 1
      if cnt[c] < 0:
        return False
    return True

class Solution {
  public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
      return false;
    }
    int[] cnt = new int[26];
    for (int i = 0; i < s.length(); ++i) {
      ++cnt[s.charAt(i) - 'a'];
      --cnt[t.charAt(i) - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      if (cnt[i] != 0) {
        return false;
      }
    }
    return true;
  }
}

class Solution {
public:
  bool isAnagram(string s, string t) {
    if (s.size() != t.size()) {
      return false;
    }
    vector<int> cnt(26);
    for (int i = 0; i < s.size(); ++i) {
      ++cnt[s[i] - 'a'];
      --cnt[t[i] - 'a'];
    }
    return all_of(cnt.begin(), cnt.end(), [](int x) { return x == 0; });
  }
};

func isAnagram(s string, t string) bool {
  if len(s) != len(t) {
    return false
  }
  cnt := [26]int{}
  for i := 0; i < len(s); i++ {
    cnt[s[i]-'a']++
    cnt[t[i]-'a']--
  }
  for _, v := range cnt {
    if v != 0 {
      return false
    }
  }
  return true
}

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) {
    return false;
  }
  const cnt = new Array(26).fill(0);
  for (let i = 0; i < s.length; ++i) {
    ++cnt[s.charCodeAt(i) - 'a'.charCodeAt(0)];
    --cnt[t.charCodeAt(i) - 'a'.charCodeAt(0)];
  }
  return cnt.every(x => x === 0);
}

impl Solution {
  pub fn is_anagram(s: String, t: String) -> bool {
    let n = s.len();
    let m = t.len();
    if n != m {
      return false;
    }
    let mut s = s.chars().collect::<Vec<char>>();
    let mut t = t.chars().collect::<Vec<char>>();
    s.sort();
    t.sort();
    for i in 0..n {
      if s[i] != t[i] {
        return false;
      }
    }
    true
  }
}

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
  if (s.length !== t.length) {
    return false;
  }
  const cnt = new Array(26).fill(0);
  for (let i = 0; i < s.length; ++i) {
    ++cnt[s.charCodeAt(i) - 'a'.charCodeAt(0)];
    --cnt[t.charCodeAt(i) - 'a'.charCodeAt(0)];
  }
  return cnt.every(x => x === 0);
};

public class Solution {
  public bool IsAnagram(string s, string t) {
    if (s.Length != t.Length) {
      return false;
    }
    int[] cnt = new int[26];
    for (int i = 0; i < s.Length; ++i) {
      ++cnt[s[i] - 'a'];
      --cnt[t[i] - 'a'];
    }
    return cnt.All(x => x == 0);
  }
}

int cmp(const void* a, const void* b) {
  return *(char*) a - *(char*) b;
}

bool isAnagram(char* s, char* t) {
  int n = strlen(s);
  int m = strlen(t);
  if (n != m) {
    return 0;
  }
  qsort(s, n, sizeof(char), cmp);
  qsort(t, n, sizeof(char), cmp);
  return !strcmp(s, t);
}

方法二

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

impl Solution {
  pub fn is_anagram(s: String, t: String) -> bool {
    let n = s.len();
    let m = t.len();
    if n != m {
      return false;
    }
    let (s, t) = (s.as_bytes(), t.as_bytes());
    let mut count = [0; 26];
    for i in 0..n {
      count[(s[i] - b'a') as usize] += 1;
      count[(t[i] - b'a') as usize] -= 1;
    }
    count.iter().all(|&c| c == 0)
  }
}

bool isAnagram(char* s, char* t) {
  int n = strlen(s);
  int m = strlen(t);
  if (n != m) {
    return 0;
  }
  int count[26] = {0};
  for (int i = 0; i < n; i++) {
    count[s[i] - 'a']++;
    count[t[i] - 'a']--;
  }
  for (int i = 0; i < 26; i++) {
    if (count[i]) {
      return 0;
    }
  }
  return 1;
}