LeetCode-Python-1392. 最长快乐前缀（暴力法 + 字符串hash）
179 浏览量
2020-12-21
20:30:05
上传
评论
收藏 48KB PDF 举报
LeetCode-Python-1392. 最长快乐前缀（暴力法最长快乐前缀（暴力法 + 字符串字符串
hash））
「快乐前缀」是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。
给你一个字符串 s，请你返回它的 最长快乐前缀。
如果不存在满足题意的前缀，则返回一个空字符串。
示例 1：
输入：s = “level”
输出：”l”
解释：不包括 s 自己，一共有 4 个前缀（”l”, “le”, “lev”, “leve”）和 4 个后缀（”l”, “el”, “vel”, “evel”）。最长的既是前缀也是后缀
的字符串是 “l” 。
示例 2：
输入：s = “ababab”
输出：”abab”
解释：”abab” 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。
示例 3：
输入：s = “leetcodeleet”
输出：”leet”
示例 4：
输入：s = “a”
输出：””
提示：
1 <= s.length <= 10^5
s 只含有小写英文字母
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-happy-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
第一种思路：
暴力解来一发试一哈，居然能过！
时间复杂度：O（N^2)
空间复杂度：O（N）
class Solution(object):
def longestPrefix(self, s):
"""
:type s: str
:rtype: str
"""
res = ""
for i in range(len(s) -1, -1, -1):
if s[:i] == s[-i:]:
res = s[:i] break
return res if res != s else ""
第二种思路：
上字符串hash的算法，
把每一个字符串转换为P进制下的一个数字，再将得到数字对M取模来计算一个hash值，
通过适当的P、M取值尽可能让每一个字符串和hash值一一对应，这样每次比较数字就可以在O(1)的时间里知道字串是否相
同。
在此取 P = 131， M = 10 ** 9 + 7。
1. 为了计算prefix的值，
资源评论
weixin_38715831
- 粉丝: 4
- 资源: 991
最新资源
- XILINXFPGA源码Xilinxspratan3xcs100E(VGAPS2)
- XILINXFPGA源码XilinxSPARTAN-3E入门开发板实例
- XILINXFPGA源码XilinxSdramVerilog和VHDL版本文档
- 物联网智能家居方案-基于Nucleo-STM32L073&机智云(大赛作品，文档齐全，可直接运行)(文档加Matlab源码)
- XILINXFPGA源码XilinxISE9.xFPGACPLD设计源码
- 成都市地图含高新区（高新南区，高新西区），天府新区，东部新区虚拟行政区划
- XILINXFPGA源码XilinxEDK设计试验
- XILINXFPGA源码XilinxEDKMicroBlaze内置USB固件程序
- 基于 django 的视频点播后台管理系统源代码+数据库
- 基于Java的网上医院预约挂号系统的设计与实现(部署视频)-kaic.mp4
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
