LWC 52:686. Repeated String Match

LWC 52:686. Repeated String Match

传送门:686. Repeated String Match

Problem:

Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1. For example, with A = “abcd” and B = “cdabcdab”. Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times (“abcdabcd”).

Note:

The length of A and B will be between 1 and 10000.

思路: 重复多少次之后能够使得A包含B,关键在于何时停止重复,显然,如果A的repeat后的长度大于B时,即可停止搜索了,因为在此长度下A都不能包含B,那么repat的次数再大也没用。

代码如下:

    public int repeatedStringMatch(String A, String B) {
        int nb = B.length();
        int na = A.length();
        int times = nb / na + 2;
        StringBuilder sb = new StringBuilder(A);
        for (int i = 1; i <= times; ++i) {
            if (sb.toString().contains(B)) return i;
            else {
                sb.append(A);
            }
        }
        return -1;
    }

times的上界可以设置的大点,当然+2已经是最紧的上界了。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之复杂链表的复制(九度OJ1524)

题目描述: 输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点)。 输入: 输入可能包含多个测试样例,输入以...

1799
来自专栏Redis

Redis类型之sorted sets类型

Redis类型之sorted sets类型

1884
来自专栏King_3的技术专栏

leetcode-166-分数到小数(用余数判断有没有出现小数的循环体)

给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以字符串形式返回小数。

1185
来自专栏C/C++基础

数组的全排列

学过数学的人都知道,全排列的意思是什么。现在如何用计算机的编程语言实现数组的全排列呢?

751
来自专栏desperate633

LintCode 子集题目代码

742
来自专栏计算机视觉与深度学习基础

Leetcode 127 Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the...

19310
来自专栏机器学习和数学

[数据结构与算法] 链接表总结

上一次说到了顺序表,链接表和顺序表一样,也是线性表。那为什么有了线性表还要有链接表呢?总之就是当数据过大时,顺序表存在一些存储方面的限制,而链接表比顺序表要更有...

2727
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-day06-知识点回顾与练习

Java基础-day06-知识点回顾与练习 1.求和案例 ? 实现代码: package StudentJavaSEday06; public class De...

2883
来自专栏数据结构与算法

后缀自动机经典操作

1504
来自专栏机器学习入门

LWC 60:736. Parse Lisp Expression

LWC 60:736. Parse Lisp Expression 传送门:736. Parse Lisp Expression Problem: You a...

1707

扫码关注云+社区