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

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

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

首先,字母异位词是指由相同字母以不同顺序组成的单词或短语。例如,“ate”, “eat”, 和 “tea” 是互为字母异位词的单词,因为它们都包含相同的字母 ‘a’、‘e’ 和 ‘t’,只是字母的顺序不同。

你需要编写一个函数来:

输入:一个字符串数组 strs,其中包含一系列单词。

处理:将这些单词分组,使得每一组内的单词都互为字母异位词。

输出:分组后的单词列表,这是一个列表的列表,其中每个子列表包含一组互为字母异位词的单词。

输入格式
  • strs:一个字符串数组。
输出格式
  • 返回一个列表,每个子列表包含所有的字母异位词。

示例

示例 1
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

解释:

单词 “eat”, “tea”, 和 “ate” 互为字母异位词,因此它们被分为一组。

单词 “tan” 和 “nat” 互为字母异位词,所以它们被分为另一组。

单词 “bat” 自身独立成组,因为没有其他单词与其构成字母异位词。

示例 2
输入: strs = [""]
输出: [[""]]

算法分析

方法一:排序数组分类

解题步骤
  1. 创建哈希表:使用字典来组织异位词,键是排序后的单词,值是原单词的列表。
  2. 遍历字符串数组:对每个字符串排序,将排序后的字符串作为键,原字符串加入对应的列表。
  3. 输出结果:将哈希表的所有值转为列表输出。
完整的规范代码
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"]))
算法分析
  • 时间复杂度:(O(nk \log k)),其中 (n) 是字符串的数量,(k) 是字符串的最大长度。
  • 空间复杂度:(O(nk)),用于存储哈希表。

方法二:计数作为键

解题步骤
  1. 使用计数数组:对每个字符串,使用长度为26的计数数组(针对26个英文字母)来统计每个字母的出现次数。
  2. 转换为元组作为键:将计数数组转换为元组,用作哈希表的键。
  3. 分类存储:根据计数元组将字符串归类到对应的列表。
完整的规范代码
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"]))
算法分析
  • 时间复杂度:(O(nk)),其中 (n) 是字符串数量,(k) 是字符串的最大长度。
  • 空间复杂度:(O(nk)),用于存储哈希表。

方法三:质数乘积作为键

解题步骤
  1. 使用质数:将26个英文字母映射到26个质数上。
  2. 计算哈希值:每个字符串通过其字符对应的质数的乘积得到一个

哈希值。

3. 分类存储:根据哈希值将字符串归类到对应的列表。

完整的规范代码
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"]))
算法分析
  • 时间复杂度:(O(nk)),其中 (n) 是字符串的数量,(k) 是字符串的平均长度。
  • 空间复杂度:(O(nk)),主要用于存储输出结果。

方法四:改进的计数法

解题步骤
  1. 优化计数表示:与方法二相同,但使用字符串表示计数数组,减少转换开销。
  2. 使用字符串键:直接将计数数组转换成字符串形式,作为哈希键使用。
完整的规范代码
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"]))
算法分析
  • 时间复杂度:(O(nk)),其中 (n) 是字符串的数量,(k) 是字符串的平均长度。
  • 空间复杂度:(O(nk)),用于存储哈希表。

方法五:排序后哈希

解题步骤
  1. 直接排序:每个字符串排序,排序后的字符串作为键。
  2. 哈希表存储:相同排序结果的字符串归为一组。
完整的规范代码
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"]))
算法分析
  • 时间复杂度:(O(nk \log k)),其中 (n) 是字符串的数量,(k) 是字符串的最大长度。
  • 空间复杂度:(O(nk)\

),用于存储哈希表和结果列表。

不同算法的优劣势对比

特征 方法一:排序数组分类 方法二:计数作为键 方法三:质数乘积作为键 方法四:改进的计数法 方法五:排序后哈希
时间复杂度 (O(nk \log k)) (O(nk)) (O(nk)) (O(nk)) (O(nk \log k))
空间复杂度 (O(nk)) (O(nk)) (O(nk)) (O(nk)) (O(nk))
优势 - 实现简单
- 易于理解
- 更快的运行时间
- 无需排序
- 唯一性好,冲突概率低
- 空间效率高
- 计数转字符串快
- 空间效率更优
- 代码简洁
- 实现直观
劣势 - 排序开销大 - 计数数组转换开销 - 质数映射复杂度高 - 字符串操作开销 - 排序时间开销大
适用场景 - 简单场景
- 教学演示
- 性能要求较高场景 - 避免哈希冲突场景 - 大数据量优化 - 代码简洁优先场景

在选择合适的方法时,应考虑实际的需求和问题规模。例如,对于需要快速处理的应用场景,可以选择计数作为键的方法;而对于需要代码简洁且易于理解的场景,则可以考虑排序后哈希的方法。对于需要避免哈希表冲突的复杂应用,质数乘积作为键提供了一个有趣的解决方案。

典型应用

字母异位词分组的应用示例覆盖了多个领域,包括数据处理、安全领域、文本分析等。这些应用不仅展示了算法的实用性,而且提供了对其在现实世界中的实际应用的洞见。

应用示例一:搜索引擎优化

场景描述

在搜索引擎技术中,快速识别并聚类含有相同字母的关键词(异位词)可以显著提高搜索结果的相关性和质量。例如,用户搜索“listen”的结果应该能够包含与“silent”相关的内容,因为它们是字母异位词。

实现步骤
  1. 关键词预处理:对搜索引擎数据库中的所有关键词进行异位词分组处理,创建一个从排序关键词到原始关键词列表的映射。
  2. 查询优化
  • 当用户提交一个搜索查询时,对查询词进行排序。
  • 查找排序后与之匹配的所有异位词组,将这些词包括在搜索结果中。
代码示例
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'

应用示例二:安全审计

场景描述

在安全审计中,确保没有敏感词被无意识地使用是非常重要的。通过将敏感词库扩展为包含所有可能的字母异位词,可以增强审计过程的全面性,例如防止某些敏感信息在加密通讯中被隐藏。

实现步骤
  1. 敏感词库扩展:将所有敏感词及其异位词形式都纳入审计字典。
  2. 通讯内容检查:审查通过的所有消息都要检查是否包含这些敏感词或其异位词。
代码示例
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

算法优势与挑战

这些应用示例突出显示了字母异位词分组算法的多功能性和实用性。利用这种算法可以在不同场景下提供精确、高效的解决方案。然而,这也带来了一些挑战,如处理大数据集时的性能优化,以及在多语言环境中的应用适配等。通过不断优化算法实现和扩展其应用范围,可以更好地满足现实世界复杂多变的需求。


欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
6天前
|
机器学习/深度学习 数据采集 搜索推荐
Python基于深度学习算法实现图书推荐系统项目实战
Python基于深度学习算法实现图书推荐系统项目实战
|
2天前
|
数据库 开发者 Python
实战指南:用Python协程与异步函数优化高性能Web应用
【7月更文挑战第15天】Python的协程与异步函数优化Web性能,通过非阻塞I/O提升并发处理能力。使用aiohttp库构建异步服务器,示例代码展示如何处理GET请求。异步处理减少资源消耗,提高响应速度和吞吐量,适用于高并发场景。掌握这项技术对提升Web应用性能至关重要。
23 10
|
1天前
|
并行计算 监控 数据处理
构建高效Python应用:并发与异步编程的实战秘籍,IO与CPU密集型任务一网打尽!
【7月更文挑战第16天】Python并发异步提升性能:使用`asyncio`处理IO密集型任务,如网络请求,借助事件循环实现非阻塞;`multiprocessing`模块用于CPU密集型任务,绕过GIL进行并行计算。通过任务类型识别、任务分割、避免共享状态、利用现代库和性能调优,实现高效编程。示例代码展示异步HTTP请求和多进程数据处理。
16 8
|
8天前
|
机器学习/深度学习 监控 算法
Python数据分析与机器学习在金融风控中的应用
Python数据分析与机器学习在金融风控中的应用
35 12
|
1天前
|
存储 缓存 安全
Python元组不可变序列的奥秘与应用方式
Python 中的元组(Tuple)是一种有序的、不可变的数据结构,它是序列的一种特殊形式,就像一个固定大小的盒子,一旦放入物品就无法更换或移除。 元组可以包含任何类型的数据,如数字、字符串甚至是其他元组。 相比列表,元组在很多场景下提供了更高效、安全的选择。
|
6天前
|
分布式计算 并行计算 算法
探索排序的宇宙奥秘:Python中归并排序的并行处理与分布式应用!
【7月更文挑战第11天】归并排序是一种分治算法,适用于并行和分布式处理。在Python中,利用`concurrent.futures`可实现并行归并排序,但因GIL限制,可能需借助`multiprocessing`或GPU库。分布式归并排序则通过分布式框架如Apache Spark处理大规模数据,每个节点独立排序后进行网络合并。并行与分布式技术提升了处理大数据的速度和效率。**
17 9
|
2天前
|
大数据 数据处理 API
性能飞跃:Python协程与异步函数在数据处理中的高效应用
【7月更文挑战第15天】在大数据时代,Python的协程和异步函数解决了同步编程的性能瓶颈问题。同步编程在处理I/O密集型任务时效率低下,而Python的`asyncio`库支持的异步编程利用协程实现并发,通过`async def`和`await`避免了不必要的等待,提升了CPU利用率。例如,从多个API获取数据,异步方式使用`aiohttp`并发请求,显著提高了效率。掌握异步编程对于高效处理大规模数据至关重要。
15 4
|
1天前
|
前端开发 JavaScript UED
Python Web应用中的WebSocket实战:前后端分离时代的实时数据交换
【7月更文挑战第16天】在前后端分离的Web开发中,WebSocket解决了实时数据交换的问题。使用Python的Flask和Flask-SocketIO库,后端创建WebSocket服务,监听并广播消息。前端HTML通过JavaScript连接到服务器,发送并显示接收到的消息。WebSocket适用于实时通知、在线游戏等场景,提升应用的实时性和用户体验。通过实战案例,展示了如何实现这一功能。
|
1天前
|
JavaScript 前端开发 UED
WebSocket在Python Web开发中的革新应用:解锁实时通信的新可能
【7月更文挑战第16天】WebSocket是实现Web实时通信的协议,与HTTP不同,它提供持久双向连接,允许服务器主动推送数据。Python有多种库如websockets和Flask-SocketIO支持WebSocket开发。使用Flask-SocketIO的简单示例包括定义路由、监听消息事件,并在HTML中用JavaScript建立连接。WebSocket提高了实时性、减少了服务器压力,广泛应用于聊天、游戏等场景。
10 1
|
3天前
|
消息中间件 安全 数据处理
Python中的并发编程:理解多线程与多进程的区别与应用
在Python编程中,理解并发编程是提高程序性能和响应速度的关键。本文将深入探讨多线程和多进程的区别、适用场景及实际应用,帮助开发者更好地利用Python进行并发编程。