这是悦乐书的第 289 次更新, 第 307 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 156 题 (顺位题号是 686). 给定两个字符串 A 和 B, 找到 A 必须重复的最小次数, 使得 B 是它的子字符串. 如果没有这样的解决方案, 返回 - 1. 例如:
输入: A ="abcd",B ="cdabcdab".
输出: 3
说明: 因为重复 A 三次 ("abcdabcdabcd"),B 是它的子串; 和 B 不是 A 重复两次的子串 ("abcdabcd").
注意: A 和 B 的长度在 1 到 10000 之间.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
特殊情况: 如果 B 的长度为 0, 直接返回 0.
正常情况: 使用循环, 依次累加 A, 然后判断在累加后的字符串中是否存在字符串 B, 借助 indexOf 方法实现, 同时统计累加的次数, 如果能够找到, 就返回最后的次数. 但是有一种情况需要考虑, 如果 B 根本就不是由 A 多次累加组成, 那么循环就容易变成死循环, 所以, 在循环外面我们取得 A 和 B 的长度之商, 如果 count 比商要大 2, 就直接返回 - 1.
- public int repeatedStringMatch(String A, String B) {
- if (B.length() == 0) {
- return 0;
- }
- int len = B.length()/A.length();
- int count = 1;
- String C = A;
- while (C.indexOf(B) <0) {
- C += A;
- count++;
- if (count-len> 2) {
- return -1;
- }
- }
- return count;
- }
03 第二种解法
在第一种解法的基础上, 我们还可以再优化下. 依旧使用循环, 只要 A 的长度小于 B 的长度, 就累加一次 A, 并记数, 然后开始判断累加后的 A 与 B 是否存在 B 是 A 的子串的关系. 如果在 A 中能够直接找到 B, 就返回 count; 如果需要再累加一次 A 才能找到 B, 那么就返回 count 加 1; 如果前面两种情况都不符合, 就返回 - 1.
- public int repeatedStringMatch(String A, String B) {
- int count = 1;
- StringBuilder sb = new StringBuilder(A);
- while (sb.length() <B.length()) {
- sb.append(A);
- count++;
- }
- if (sb.indexOf(B)>= 0) {
- return count;
- }
- if (sb.append(A).indexOf(B)>= 0) {
- return count+1;
- }
- return -1;
- }
04 小结
算法专题目前已日更超过四个月, 算法题文章 157 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/222be442d5f3