前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 686. 重复叠加字符串匹配

Leetcode 686. 重复叠加字符串匹配

作者头像
zhipingChen
发布2019-05-15 11:07:48
7390
发布2019-05-15 11:07:48
举报
文章被收录于专栏:编程理解

题目描述

给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数,使得字符串B成为叠加后的字符串A的子串,如果不存在则返回 -1。

示例 1:

输入: A = "abcd",B = "cdabcdab"

输出: 3

解释: 因为 A 重复叠加三遍后为 “abcdabcdabcd”,此时 B 是其子串;A 重复叠加两遍后为"abcdabcd",B 并不是其子串。

解法

这里以 len(A) 表示字符串 A 的长度

len(A) > len(B)
len(A) > len(B)

时,如果 B 不是 A 或者 A + A 的子串,则返回 -1

len(A) = len(B)
len(A) = len(B)

时,如果 B 不是 A 或者 A + A 的子串,则返回 -1

len(A) < len(B)
len(A) < len(B)

时,不妨设存在

n
n

,满足

len(n*A) \ge len(B)
len(n*A) \ge len(B)

,且

len((n-1)*A) < len(B)
len((n-1)*A) < len(B)

,如果 B 不是 n*A 或者 (n+1)*A 的子串,则返回 -1

代码语言:javascript
复制
import math
class Solution:
    def repeatedStringMatch(self, A: str, B: str) -> int:
        if len(set(A))<len(set(B)):
            return -1
        c=math.ceil(len(B)/len(A))
        for i in range(2):
            if B in A*(c+i):
                return c+i
        return -1

若 B 是 重复叠加 A 后的子串,则 A 字符串的字符集应包含 B 字符串的字符集,即

len(set(A)) \ge len(set(B))
len(set(A)) \ge len(set(B))

。因为

c=math.ceil(len(B)/len(A))
c=math.ceil(len(B)/len(A))

,则有

len(c*A) \ge len(B)
len(c*A) \ge len(B)

,根据上述情况描述,如果 B 不是 c*A 或者 (c+1)*A 的子串,则返回 -1,否则返回重复次数。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019.05.06 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档