leetcode每日一题 python解法 4月19日

难度:困难

题目内容:

由 n 个连接的字符串 s 组成字符串 S,记作 S = [s,n]。例如,["abc",3]=“abcabcabc”。

如果我们可以从 s2 中删除某些字符使其变为 s1,则称字符串 s1 可以从字符串 s2 获得。例如,根据定义,"abc" 可以从 “abdbec” 获得,但不能从 “acbbe” 获得。

现在给你两个非空字符串 s1 和 s2(每个最多 100 个字符长)和两个整数 0 ≤ n1 ≤ 106 和 1 ≤ n2 ≤ 106。现在考虑字符串 S1 和 S2,其中 S1=[s1,n1] 、S2=[s2,n2] 。

请你找出一个可以满足使[S2,M] 从 S1 获得的最大整数 M 。

示例:

输入:
s1 ="acb",n1 = 4
s2 ="ab",n2 = 2

返回:
2

题解:

看着逻辑蛮简单的啊。。。。为啥是困难咧

class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        s2m = s2 * n2
        s2mc = s2m
        M = 0
        for s in s1*n1:
            if s2mc == "":
                s2mc = s2m
                M += 1
            if s == s2mc[0]:
                s2mc = s2mc[1:]
        if s2mc == "":
            M += 1
        return M

然后放进去果然超时了,超时的输入是

"lovelive"
100000
"lovelive"
100000

看来这么简单的直接遍历是不行的
那就重新来分析以下,先看几段s1能包含完整的s2
可能的情况是s1包含了完整的s2,或者某段s2前半部分在前一s1的结尾,后半部分在s1的开头

class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        s2c = s2
        s1num = 0
        while s2c:
            s1num += 1
            if s2c == "":
                break
            for s in s1:
                if s == s2c[0]:
                    s2c = s2c[1:]

        #s1num段s1包含了一段s2
        if s1num == 1:
            s2num = 0
            s2c = s2
            for s in s1:
                if s == s2c[0]:
                    s2c = s2c[1:]
                if s2c == "":
                    s2c = s2
                    s2num += 1
            #每段s1包含s2num段s2
            #验证一下有没有跨的
            s2num2 = 0
            s2c = s2
            for s in s1*2:
                if s == s2c[0]:
                    s2c = s2c[1:]
                if s2c == "":
                    s2c = s2
                    s2num2 += 1
            if s2num2 == s2num*2:#说明不跨越
                return n1*s2num // n2 
            else:
                return (n1*s2num + (n1-1)*(s2num2 - s2num*2)) // n2

        else:
            return n1//s1num//n2

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,421评论 0 2
  • String类 1、String对象的初始化 由于String对象特别常用,所以在对String对象进行初始化时,...
    简诗阅读 408评论 0 1
  • 字符串格式:s1 = 'adf\nsd',类型为str 原始字符串:在字符串的第一个引号前加上字母“ r ”(不区...
    往日_07ae阅读 428评论 0 0
  • 数据类型 数值整数浮点数简单数学函数随机函数三角函数 布尔类型 字符串 列表 元组 字典 Python数据类型 数...
    MetaT1an阅读 423评论 1 1
  • 数值型函数 abs(x) 绝对值 abs(-9)=9comb(n,k) 从n中取k个的组合 comb(1...
    战歌阅读 33,217评论 0 21