LeetCode 题目 49：字母异位词分组 5种算法实现与典型应用案例【python】

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

输入: strs = [""]
输出: [[""]]

def groupAnagrams(strs):
    """
    使用哈希表根据排序后的字符串分类字母异位词
    :param strs: List[str], 输入的字符串数组
    :return: List[List[str]], 分组后的字母异位词列表
    """
    anagram_map = {}
    for s in strs:
        sorted_s = ''.join(sorted(s))
        if sorted_s not in anagram_map:
            anagram_map[sorted_s] = [s]
        else:
            anagram_map[sorted_s].append(s)
    return list(anagram_map.values())
# 示例调用
print(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

def groupAnagrams(strs):
    """
    使用字符计数数组作为哈希表键来分类字母异位词
    :param strs: List[str], 输入的字符串数组
    :return: List[List[str]], 分组后的字母异位词列表
    """
    anagram_map = {}
    for s in strs:
        count = [0] * 26  # 对应26个英文字母
        for char in s:
            count[ord(char) - ord('a')] += 1
        count_tuple = tuple(count)
        if count_tuple not in anagram_map:
            anagram_map[count_tuple] = [s]
        else:
            anagram_map[count_tuple].append(s)
    return list(anagram_map.values())
# 示例调用
print(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

def groupAnagrams(strs):
    """
    使用质数乘积作为哈希键来分类字母异位词
    :param strs: List[str], 输入的字符串数组
    :return: List[List[str]], 分组后的字母异位词列表
    """
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
    anagram_map = {}
    for s in strs:
        key = 1
        for char in s:
            key *= primes[ord(char) - ord('a')]
        if key not in anagram_map:
            anagram_map[key] = [s]
        else:
            anagram_map[key].append(s)
    return list(anagram_map.values())
# 示例调用
print(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

def groupAnagrams(strs):
    """
    使用改进的计数法（字符串键）分类字母异位词
    :param strs: List[str], 输入的字符串数组
    :return: List[List[str]], 分组后的字母异位词列表
    """
    anagram_map = {}
    for s in strs:
        count = [0] * 26
        for char in s:
            count[ord(char) - ord('a')] += 1
        key = '#'.join(map(str, count))  # 将计数数组转换为字符串形式
        if key not in anagram_map:
            anagram_map[key] = [s]
        else:
            anagram_map[key].append(s)
    return list(anagram_map.values())
# 示例调用
print(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

def groupAnagrams(strs):
    """
    使用字符串排序后作为哈希键来分类字母异位词
    :param strs: List[str], 输入的字符串数组
    :return: List[List[str]], 分组后的字母异位词列表
    """
    anagram_map = {}
    for s in strs:
        key = ''.join(sorted(s))
        if key not in anagram_map:
            anagram_map[key] = [s]
        else:
            anagram_map[key].append(s)
    return list(anagram_map.values())
# 示例调用
print(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

def preprocess_keywords(keywords):
    anagram_map = {}
    for keyword in keywords:
        sorted_keyword = ''.join(sorted(keyword))
        if sorted_keyword not in anagram_map:
            anagram_map[sorted_keyword] = [keyword]
        else:
            anagram_map[sorted_keyword].append(keyword)
    return anagram_map
def search(query, anagram_map):
    sorted_query = ''.join(sorted(query))
    return anagram_map.get(sorted_query, [])
# 示例关键词库和搜索
keywords = ["listen", "silent", "enlist", "google", "gooegl"]
anagram_map = preprocess_keywords(keywords)
print(search("tinsel", anagram_map))  # 输出: ['listen', 'silent', 'enlist'

def expand_sensitive_words(words):
    expanded_dict = {}
    for word in words:
        permutations = groupAnagrams([word])
        for perm in permutations[0]:
            expanded_dict[perm] = True
    return expanded_dict
def audit_communication(message, sensitive_dict):
    words = message.split()
    for word in words:
        if ''.join(sorted(word)) in sensitive_dict:
            return False
    return True
# 审计示例
sensitive_words = ["example", "word"]
sensitive_dict = expand_sensitive_words(sensitive_words)
message = "This is a simple wodr and an eaxmple."
print(audit_communication(message, sensitive_dict))  # 输出: False