赞
踩
专栏《LeetCode|一刷到底》
打卡每天leetcode精选每日一题(尽量不断更!)
点击关注不迷路!!!
- 题目:重复叠加字符串匹配
- 难度:中等
- 描述:给定两个字符串 a 和 b,寻找重复叠加字符串 a 的最小次数,使得字符串 b 成为叠加后的字符串 a 的子串,如果不存在则返回 -1。
注意:字符串 “abc” 重复叠加 0 次是 “”,重复叠加 1 次是 “abc”,重复叠加 2 次是 “abcabc”。- 示例1
输入:a = “abcd”, b = “cdabcdab”
输出:3
解释:a 重复叠加三遍后为 “abcdabcdabcd”, 此时 b 是其子串。
- 示例2
输入:a = “a”, b = “aa”
输出:2
- 示例3
输入:a = “abc”, b = “wxyz”
输出:-1
本题并不需要用到多么高深的算法,题中的中心思想在于对多个a字符串进行叠加,由此不难想到如果想要满足所有情况至少需要叠加多少个a,找到这个数量之后每次构建出最长的备选字符串new_str,从左到右遍历new_str在字符串new_str中找到了字符串b之后统计剩余子串中有多少个完整的字符串a,减去其个数即可。
构建最长的字符串new_str
考虑如下的情况不难得到当new_str的长度为len(b)//len(a)+2
的时候可以满足任何情况(a的长度大于b时另作考虑)
当构建好了new_str时,new_str中包含没用到的字符串a时的情形如下:
解法(一)
按照解析中的方法进行代码编写如下:
class Solution: def repeatedStringMatch(self, a: str, b: str) -> int: # 得到满足任何条件的最小叠加字符串new_str # 如果a可以作为子串,此时的new_str中一定含有正确答案 res = len(b) // len(a) if len(b) // len(a) != 0 else 1 new_str = a * (res + 2) for i in range(len(new_str) - len(b) + 1): if new_str[i] == b[0]: # 当能在new_str中找到b时进行判断 if new_str[i:i + len(b)] == b: # 从后面看,剩余长度超过2*len(a)的情况 if len(new_str) - i - len(b) >= 2 * len(a): return res # 长度超过len(a)的情况 elif len(new_str) - i - len(b) >= len(a): return res + 1 else: return res + 2 return -1
解法(二)
直接使用Python中的字符串判断(a in b
)方法进行编写:
class Solution:
def repeatedStringMatch(self, a: str, b: str) -> int:
min = len(b) // len(a)
for i in range(min, min + 3):
if b in a * i:
return i
return -1
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。