专栏首页编程理解Leetcode 686. 重复叠加字符串匹配

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

题目描述

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

示例 1:

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

输出: 3

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

解法

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

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

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

时,不妨设存在

,满足

,且

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

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 字符串的字符集,即

。因为

,则有

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 3. 无重复字符的最长子串

    输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

    zhipingChen
  • Leetcode 687. 最长同值路径

    给定一个二叉树,找到最长的路径,这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

    zhipingChen
  • Leetcode 696. 计数二进制子串

    给定一个字符串 s,计算具有相同数量0和1的非空(连续)子字符串的数量,并且这些子字符串中的所有0和所有1都是组合在一起的。

    zhipingChen
  • 【Redis面试题】Redis的字符串是怎么实现的?

    年前本人在找工作面试时在Redis相关问题上可栽了跟头。在面试前按常规套路准备了一下,比如 Redis 的常用5种数据结构,Redis持久化策略,Redis实现...

    用户4447430
  • Java 编码代码规范

    2、变量名要符合规范,通俗易懂,例如:记录日志的字符串 就叫 logMessage,不要叫或者加什么str 了。

    用户2141593
  • 面试:你知道Redis的字符串是怎么实现的吗?

    面试官 :看你简历上写了熟悉常用数据结构,都有哪些说说 本人 :常用有5种,string,list,set,zset,hash(内心很得意)

    IT大咖说
  • 实现MD5加密

    /**  * 实现MD5加密  *  */ public class MD5 {  /**   * 获取加密后的字符串   * @param ...

    用户1220053
  • 消息队列中间件(三)Kafka 入门指南

    Kafka的前身是由LinkedIn开源的一款产品,2011年初开始开源,加入了 Apache 基金会,2012年从 Apache Incubator 毕业变成...

    未读代码
  • 10个有关String的面试问题

    简单来讲,“==”测试的是两个对象的引用是否相同,而equals()比较的是两个字符串的值是否相等。除非你想检查的是两个字符串是否是同一个对象,否则你应该使用e...

    哲洛不闹
  • 慢讯!Sharding-Sphere 正式进入 Apache 孵化器

    美国时间2018年11月10日,开源分布式数据库中间件生态圈Sharding-Sphere正式进入Apache基金会孵化器。

    芋道源码

扫码关注云+社区

领取腾讯云代金券