字母異位詞

一、字母異位詞是什麼意思

字母異位詞指的是由相同的字母組成，但字母位置不同的兩個單詞或短語。比如，“heart”和“earth”就是字母異位詞。

在很多實際應用中，需要對字符串進行判斷是否是字母異位詞。比如在數據清洗過程中，需要去除重複的記錄，就可以使用字母異位詞的概念。

二、字母異位詞分組

給定一個字符串數組，將字母異位詞組合在一起，輸出排好序的分組。比如，給定一個字符串數組 [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]，輸出結果為：[ [“ate”,”eat”,”tea”], [“nat”,”tan”], [“bat”] ]。

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        res = []
        dic = {}
        for s in strs:
            sorted_s = ''.join(sorted(s))
            if sorted_s in dic:
                dic[sorted_s].append(s)
            else:
                dic[sorted_s] = [s]
        for key in dic:
            res.append(dic[key])
        return res

上述代碼中，我們使用了一個哈希表來記錄每個排好序的字符串對應的原始字符串列表。最終遍歷哈希表，將每個列表加入結果中。時間複雜度為O(nklogk)，其中n為字符串數組的長度，k為字符串的最大長度。

三、字母異位詞分組Python

Python語言中可以使用defaultdict來簡化代碼。defaultdict可以在字典中自動初始化一些鍵的默認值，這樣就可以省略一些if判斷。

from collections import defaultdict

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        ans = defaultdict(list)
        for s in strs:
            ans[tuple(sorted(s))].append(s)
        return ans.values()

四、字母異位詞判斷C語言

在C語言中，可以使用哈希表來判斷兩個字符串是否是字母異位詞。

#include 
#include 

#define MAX_LEN 100005
#define BASE 127

int hash[MAX_LEN];

int main() {
    int n;
    char s[MAX_LEN];
    scanf("%d", &n);
    while (n--) {
        scanf("%s", s);
        int len = strlen(s), sum = 0;
        for (int i = 0; i < len; i++) {
            sum += s[i];
        }
        if (hash[sum]) {
            printf("%s is an anagram of %s\n", s, hash[sum]);
        } else {
            hash[sum] = s;
        }
    }
    return 0;
}

上述代碼中，我們使用一個全局哈希表來記錄每個字符串對應的ascii碼總和。遍歷每個字符串時，計算其ascii碼總和並在哈希表中查找是否已經存在相同ascii碼總和的字符串。如果有，則說明這兩個字符串是字母異位詞，輸出即可。否則，將當前字符串的信息存入哈希表中。

五、字母異位詞可以用ASCII總和來寫嗎

上述C語言代碼的思路是使用ascii碼總和來判斷字母異位詞。但這種方法並不可靠，因為不同的字符串可以有相同的ascii碼總和。

比如，字符串”aa”和”bb”的ascii碼總和都是194。此外，這種方法還容易受到字符串長度的限制，一旦字符串長度超過了可以表示的最大值，就會出現哈希衝突。

六、有效的字母異位詞

給定兩個字符串s和t，編寫一個函數來判斷它們是否是字母異位詞。比如，s = “anagram”，t = “nagaram”，返回true；s = “rat”，t = “car”，返回false。

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False
        dic1 = {}
        dic2 = {}
        for i in range(len(s)):
            dic1[s[i]] = dic1.get(s[i], 0) + 1
            dic2[t[i]] = dic2.get(t[i], 0) + 1
        return dic1 == dic2

上述Python代碼中，我們使用兩個哈希表分別記錄兩個字符串中每個字符出現的次數。遍歷完字符串後，比較兩個哈希表是否相同即可。

七、字母異位詞搜索

給定一個字符串和一個目標字符串，判斷是否可以通過交換字符串中的字符得到目標字符串。

class Solution(object):
    def canConvert(self, source, target):
        """
        :type source: str
        :type target: str
        :rtype: bool
        """
        if len(source) != len(target):
            return False
        dic = {}
        for i in range(len(source)):
            if source[i] not in dic:
                dic[source[i]] = target[i]
            elif dic[source[i]] != target[i]:
                return False
        return len(set(target)) < 26

上述Python代碼中，我們使用一個哈希表記錄source中每個字符對應的target字符。如果存在不同的source字符對應同一個target字符的情況，那麼無法通過交換字符得到目標字符串。此外，如果target字符串中的字符種類已經超過了26種（即英文字母的數量），那麼無論如何也無法通過交換字符得到目標字符串。