Python算法:如何解决回文索引问题详解编程语言
2023-06-13 09:20:23 时间
本文由码农网 – 小峰原创翻译,转载请看清文末的转载要求,欢迎参与我们的付费投稿计划!
给定一个单词word和一个字符串S,找到S中的所有起始索引——word的回文。
例如,假设word是“ab”,并且S是“abxaba”,则返回0,3和4。
对于这个问题野蛮的解决方案是遍历S中每个单词大小的窗口并检查它们是否是回文,如下所示:
from collections import Counter def is_anagram(s1, s2): return Counter(s1) == Counter(s2) def anagram_indices(word, s): result = [] for i in range(len(s) - len(word) + 1): window = s[i:i + len(word)] if is_anagram(window, word): result.append(i) return result
这将花费O(|W| * |S|)时间。有没有更快的方法呢?
解决这个问题可以使用的一种方法是Rabin-Karp算法。基本思想是我们可以对目标word做一个基于频率的散列,并检查s下的任何窗口是否散列为相同的值。也就是说,散列将是每个字符和其频率的char * prime_num ** char_freq之和。如果word和窗口的散列匹配,则我们可以对两个字符串手动加上== 。因为预计冲突很少,所以时间将是O(S)。但是,解决这个问题有一个更简单的方法:
请注意,沿着窗口移动意味着当实际只有一小部分更新的时候,重新计算整个窗口的频率计数。这种见解引导我们采取以下策略:
制作目标单词的频率字典 当我们沿着字符串前进时,持续比较差异 当字典为空时,窗口和单词匹配我们通过增加窗口中的新字符并删除旧的字符来区分我们的频率字典。
class FrequencyDict: def __init__(self, s): self.d = {} for char in s: self.increment(char) def _create_if_not_exists(self, char): if char not in self.d: self.d[char] = 0 def _del_if_zero(self, char): if self.d[char] == 0: del self.d[char] def is_empty(self): return not self.d def decrement(self, char): self._create_if_not_exists(char) self.d[char] -= 1 self._del_if_zero(char) def increment(self, char): self._create_if_not_exists(char) self.d[char] += 1 self._del_if_zero(char) def anagram_indices(word, s): result = [] freq = FrequencyDict(word) for char in s[:len(word)]: freq.decrement(char) if freq.is_empty(): result.append(0) for i in range(len(word), len(s)): start_char, end_char = s[i - len(word)], s[i] freq.increment(start_char) freq.decrement(end_char) if freq.is_empty(): beginning_index = i - len(word) + 1 result.append(beginning_index) return result
这应该在O(S)时间运行。
欢迎继续探索其他有趣的编程问题。
译文链接:http://www.codeceo.com/article/python-anagram-indices.html
英文原文:How to Solve the Anagram Indices Problem
翻译作者:码农网 – 小峰
[ 转载必须在正文中标注并保留原文链接、译文链接和译者等信息。]
原创文章,作者:Maggie-Hunter,如若转载,请注明出处:https://blog.ytso.com/7834.html
cgojavapython相关文章
- 你一定是在逗我,Python都不会就想做算法?
- python常用面试题_Python+Selenium 常见面试题整理[通俗易懂]
- python中的 += 与 +
- Python语法详解
- 手机python 3.8解释器_Python 3.8 解释器安装教程
- python生兔子问题(递归算法)_java实现斐波那契数列
- python表情代码_Python实现表情包的代码实例[通俗易懂]
- 【说站】python聚类算法是什么
- 【说站】python文件导入相对路径
- python开发h5页面_大数据和python有关吗
- 在python中用来安装第三方库的常用工具_什么库用于安装管理Python扩展包
- python连接远程服务器_windows收不到组播
- python之代理ip的配置与调试
- Python基础语法-基本数据类型-元组(一)
- python-Python与SQLite数据库-SQLite数据库的基本知识(二)
- python实现爬虫数据存到 MongoDB
- Python轻松连接SQL Server数据库(python连接sqlserver)
- Python模块学习datetime介绍
- python定时检查启动某个exe程序适合检测exe是否挂了
- python开发的小球完全弹性碰撞游戏代码
- 深入分析在Python模块顶层运行的代码引起的一个Bug