[[413065]]

本文轉(zhuǎn)載自微信公眾號「程序員小熊」，作者程序員小熊。轉(zhuǎn)載本文請聯(lián)系程序員小熊公眾號。

前言

大家好，我是來自于華為的程序員小熊。今天給大家?guī)硪坏琅c哈希表相關(guān)的題目，這道題同時也是微軟、字節(jié)、谷歌和亞馬遜等互聯(lián)網(wǎng)大廠的面試題，即力扣上第242題-有效的字母異位詞。

本文主要介紹哈希表的策略來解答此題，供大家參考，希望對大家有所幫助。

有效的字母異位詞

給定兩個字符串 s 和 t ，編寫一個函數(shù)來判斷 t 是否是 s 的字母異位詞。 
 
注意：若 s 和 t 中每個字符出現(xiàn)的次數(shù)都相同，則稱 s 和 t 互為字母異位詞。 
 
 
示例 1： 
 
輸入: s = "anagram", t = "nagaram" 
輸出: true 
 
示例 2： 
 
輸入: s = "rat", t = "car" 
輸出: false 
  
 
提示： 
 
1 <= s.length, t.length <= 5 * 104 
s 和 t 僅包含小寫字母 

解題思路

字母異位詞：由相同的字母按照不同的順序組成的單詞。

根據(jù)上述字母異位詞的定義可知，兩個字符串要互為字母異位詞，則必須滿足一下兩個條件：

• 長度相等;
• 相同字符出現(xiàn)的次數(shù)相同。

凡是涉及到字母出現(xiàn)的頻次的相關(guān)問題，都可以考慮用哈希表去求解，可以以字母為哈希表的key，字母出現(xiàn)的次數(shù)作為哈希表的value。

舉例

以判斷 s = "anagram" 和 t = "nagaram" 是否互為字母異位詞為例子，如下圖示。

例子

定義一個數(shù)組(C 語言用數(shù)組模擬哈希表)或哈希表(C++ 等語言)，以 s[i] - 'a' 作為哈希表的 key，以 s[i] 在字符串 s 中出現(xiàn)的次數(shù)作為 value;

哈希表

遍歷字符串 s 和 t，遇到 s 中的字符時，對哈希表中記錄的 value 加 1，否則減 1;

對字符串 s 中的字符的處理

對字符串 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; 
    } 
     
    /* 數(shù)組模擬哈希表 */ 
    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 
} 

復(fù)雜度分析

時間復(fù)雜度：O(n)，其中 n 是字符串的長度，需要遍歷一遍字符串。

空間復(fù)雜度：O(S)，其中 S 為字符集大小，S = 26。