LeetCode Repeated String Match
2024-08-24 02:27:14
原题链接在这里：https://leetcode.com/problems/repeated-string-match/description/
题目：
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重复append自己知道比B长，看B是否包含在内，若包含返回当前count.
若没有再append次A. 若B能是substring, 这个长度已经可以包含所有可能性. B的开头在0到A.length()-1的任何位置都足够盖住B.
Time Complexity: O(A.length()+B.length()). create个长度为A.length()+B.length()的string. 再用B找index.
Space: O(A.length()+B.length()).
AC Java:
class Solution {
public int repeatedStringMatch(String A, String B) {
int count = 0;
StringBuilder sb = new StringBuilder();
while(sb.length() < B.length()){
sb.append(A);
count++;
}
if(sb.indexOf(B) >= 0){
return count;
}else if(sb.append(A).indexOf(B) >= 0){
return count+1;
}else{
return -1;
}
}
}
最新文章
- 久违的phpstorm
- java类加载器加载文件
- MSSQL数据库安装失败
- js让iframe高度自动
- SFTPTool 和 FTPTooL.java
- initialize or clean up your unittest within .net unit test
- packinfo-java的作用
- 1.linux下Kconfig编写规范
- oc学习之路----多级指针的使用和内存分析
- Zjnu Stadium(hdu3047带权并查集)
- POJ 3111 K Best（二分答案）
- 转帖：Html.BeginForm
- object 插入元素，插入HTML页面
- Run Loop简介
- nginx反向代理-解决前端跨域问题
- python学习3---产生随机数
- 为SNP增加种族人群频率
- KTV项目之3个ListView的跳转和加载歌手图片
- 目标检测（四）Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks
- [福建集训2011][LOJ10111]相框