Loading...
墨滴

程序员小熊

2021/07/28  阅读:49  主题:全栈蓝

哈希表妙解字母异位词

前言

大家好,我是来自于华为程序员小熊。今天给大家带来一道与哈希表相关的题目,这道题同时也是微软、字节、谷歌和亚马逊等互联网大厂的面试题,即力扣上的第242题-有效的字母异位词。

本文主要介绍哈希表的策略来解答此题,供大家参考,希望对大家有所帮助。

有效的字母异位词

给定两个字符串 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 仅包含小写字母

解题思路

字母异位词:由相同的字母按照不同的顺序组成的单词。

根据上述字母异位词的定义可知,两个字符串要互为字母异位词,则必须满足一下两个条件:

  1. 长度相等;
  2. 相同字符出现的次数相同。

凡是涉及到字母出现的频次的相关问题,都可以考虑用哈希表去求解,可以以字母为哈希表的key,字母出现的次数作为哈希表的value

举例

以判断 s = "anagram" 和 t = "nagaram" 是否互为字母异位词为例子,如下图示。

例子
例子

定义一个数组(C 语言用数组模拟哈希表)或哈希表(C++ 等语言),以 s[i] - 'a' 作为哈希表的 key,以 s[i] 在字符串 s 中出现的次数作为 value;

哈希表
哈希表

遍历字符串 s 和 t,遇到 s 中的字符时,对哈希表中记录的 value 加 1,否则减 1;

对字符串 s 中的字符的处理
对字符串 s 中的字符的处理
对字符串 t 中的字符的处理
对字符串 t 中的字符的处理

以此类推,采用哈希表的策略的完整处理过程如下动图示

哈希表处理完整过程
哈希表处理完整过程

Show me the Code

C

bool isAnagram(char * s, char * t){
    /* 判断字符串是否为空,为空则不能用 strlen 求长度 */
    if (s == NULL && t == NULL) {
        return true;
    } else if (s == NULL && t != NULL || s != NULL && t == NULL) {
        return false;
    /* 两个非空字符串长度不等,肯定不互为字母异位词 */
    } else if (strlen(s) != strlen(t)){
        return false;
    }
    
    /* 数组模拟哈希表 */
    char hash[26] = {0};
    for (int i = 0; s[i] != '\0'; ++i) {
        hash[s[i] - 'a']++;
        hash[t[i] - 'a']--;
    }

    for (int i = 0; i < 26; ++i) {
        if (hash[i] != 0) {
            return false;
        }
    }

    return true;
}

C++

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) {
        return false;
    }

    int len = s.length();
    unordered_map<int, int> record;
    for (int i = 0; i < len; ++i) {
        record[s[i] - 'a']++;
        record[t[i] - 'a']--;
    }

    for (int i = 0; i < 26; ++i) {
        if (record[i] != 0) {
            return false;
        }
    }
    
    return true;
}

Java

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }

    int[] hash = new int[26];
    for (int i = 0; i < s.length(); i++) {
        hash[s.charAt(i) - 'a']++;
        hash[t.charAt(i) - 'a']--;
    }

    for (int i : hash) {
        if (i != 0) {
            return false;
        }
    }

    return true;
}

Python3

def isAnagram(self, s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    hash = [0]*26
    for i in range(len(s)):
        hash[ord(s[i]) - ord("a")] += 1
    for i in range(len(t)):
        hash[ord(t[i]) - ord("a")] -= 1

    for i in range(26):
        if hash[i] != 0:
            return False
            
    return True

Golang

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

  var hash [26]int
  for i := range s {
    hash[s[i] - 'a']++
    hash[t[i] - 'a']--
  }

  for _, v := range hash {
    if v != 0 {
      return false
    }
  }
  
  return true
}

复杂度分析

时间复杂度:O(n),其中 n 是字符串的长度,需要遍历一遍字符串。

空间复杂度:O(S),其中 S 为字符集大小,S = 26。

往期精彩回顾

阿里云最新面试真题

只赢不亏的买股票的方法

如何快速合并两个有序数组?

更多精彩

关注公众号程序员小熊

微信公众号
微信公众号

回复512,即可获取算法小炒电子书~

回复C++,即可获取侯捷老师的 C++ 视频教程~

回复算法,即可获取高清无码的经典算法电子书~

回复python,即可获取高清无码的经典 python 电子书~

回复1024,即可获取三份来自 BAT 大佬的 Leetcode 刷题手册~

为了回馈读者,本公众号不定期会有送礼活动,敬请关注~

程序员小熊

2021/07/28  阅读:49  主题:全栈蓝

作者介绍

程序员小熊

公众号:程序员小熊,华为程序员