给定两个字符串 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
提示:
-
1 <= a.length <= 104 -
1 <= b.length <= 104 a和b由小写英文字母组成
思路分析 #
首先获取两个串的长度a, b,根据题意可知,只有两种情况,假设n为(b/a)向上取整,那么只有可能b是n倍a的子串,或者b是(n+1)倍a的子串,或者都不是,这样输出-1
Rust代码 #
impl Solution {
pub fn repeated_string_match(a: String, b: String) -> i32 {
let (lb, la) = (b.len(), a.len());
let times = ((lb as f64) / (la as f64)).ceil() as usize;
if a.repeat(times).contains(&b) {
times as i32
} else if a.repeat(times + 1).contains(&b) {
times as i32 + 1
} else {
-1
}
}
}