C#LeetCode刷题之#686-重复叠加字符串匹配(Repeated String Match)
问题
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3963 访问。
给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数,使得字符串B成为叠加后的字符串A的子串,如果不存在则返回 -1。
举个例子,A = "abcd",B = "cdabcdab"。
答案为 3, 因为 A 重复叠加三遍后为 “abcdabcdabcd”,此时 B 是其子串;A 重复叠加两遍后为"abcdabcd",B 并不是其子串。
注意:A 与 B 字符串的长度在1和10000区间范围内。
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.
示例
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3963 访问。
public class Program {
public static void Main(string[] args) {
var A = "abcd";
var B = "cdabcdab";
var res = RepeatedStringMatch(A, B);
Console.WriteLine(res);
Console.ReadKey();
}
private static int RepeatedStringMatch(string A, string B) {
var length = Math.Ceiling(B.Length / (double)A.Length) + 1;
var repeat = new StringBuilder();
for(var i = 0; i < length; i++) {
repeat.Append(A);
if(repeat.Length < B.Length) continue;
if(repeat.ToString().Contains(B)) return i + 1;
}
return -1;
}
}
以上给出1种算法实现,以下是这个案例的输出结果:
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3963 访问。
3
分析:
设字符串A的长度是 m,字符串B的长度是 n,由于部分运行库的使用,以上算法的时间复杂度应当为: 。
最新文章
- VPS拨号主机自动拨号脚本(centos7)
- java课后作业
- yii 事物
- React入门资源整理
- Java 中的resultset详解
- php __autoload使用
- redis的持久化 rdb和aof
- 在SrollView中嵌套GridView或ListView(转)
- JPA Advanced Mappings(映射)
- assert断言检测
- onselectstart属性解决双击出现的蓝色区域
- Windows &; RabbitMQ:Shovel
- YSLOW(一款实用的网站性能检测工具)
- Solidity的三种转账方式与比较
- 从PHP官方镜像创建开发镜像
- VMware Authorization Service不能启动 VMware虚拟机状态已挂起无法恢复解决方案
- 【C语言】 8421BCD码与二进制的转换
- FFT自看
- js精准时间迭代器(定时器)
- open /etc/docker/certs.d/registry.access.redhat.com/redhat-ca.crt: no such file or directory 解决方案