题目
给定两个字符串 a 和 b,寻找重复叠加字符串 a 的最小次数,使得字符串 b 成为叠加后的字符串 a 的子串,如果不存在则返回 -1。
注意:字符串 “abc” 重复叠加 0 次是 “”,重复叠加 1 次是 “abc”,重复叠加 2 次是 “abcabc”。
示例 1:
输入:a = "abcd", b = "cdabcdab" 输出:3 解释:a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。
示例 2:
输入:a = "a", b = "aa" 输出:2
示例 3:
输入:a = "a", b = "a" 输出:1
示例 4:
输入:a = "abc", b = "wxyz" 输出:-1
解题
方法一:
class Solution { public: int repeatedStringMatch(string a, string b) { string s=a; while(s.size()<b.size()){ s+=a; } s+=a; int pos=s.find(b); if(pos==string::npos) return -1; return (pos+b.size()-1)/a.size()+1; } };
注意:pos+b.size()是个数(因为从pos这个位置开始匹配的,比如pos=0,b.size()=2,那么个数就是2), 为了向上取整 因此通过 先-1然后向下整除,再加1