找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

微信名称:美国米群网

微 信 号:MeetQun

微信QQ:群: 320065698

查看: 440|回复: 3
收起左侧

[基础刷题题目讨论] 459. Repeated Substring Pattern

[复制链接]

6

主题

0

精华

58

积分

资深会员

Rank: 2

积分
58
发表于 1-11-2017 01:12 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
想法:列举从1 to length/2 的可能重复长度(a),然后一一进行判断,判断时,可以比较length/a次重复片段和原string是否equal,但这样时间过长,长string 的比较takes time. 所以对重复片段依次进行比较,一旦发现不多,就break。

  1. public class Solution {
  2.     public boolean repeatedSubstringPattern(String str) {
  3.         
  4.       int length = str.length();
  5.         if (length <2 ){
  6.             return false;
  7.         }
  8.         // loop from 1 to length/2
  9.         for (int i = 1; i <= length/2; i++){
  10.             if ((length % i) == 0){
  11.                 int copy = length/i;
  12.                 String sub = str.substring(0,i);
  13.                
  14.                 // compare sub with the following sub copies, if all equal then true, if compare sub*copy == str, time too long
  15.                 for (int j = 0; j<copy; j++){
  16.                     
  17.                         String com = str.substring(j*i,j*i+i);
  18.                     if (!sub.equals(com)){
  19.                         // should be break , not false
  20.                         break;
  21.                     }
  22.                     // should have the condition, or not true
  23.                     if (j == copy-1){
  24.                             return true;
  25.                     }
  26.                     
  27.                 }
  28.                
  29.                
  30.             }
  31.         }
  32.         return false;
  33.         
  34.     }
  35. }
复制代码

0

主题

0

精华

2

积分

新米人

Rank: 1

积分
2
发表于 1-11-2017 01:13 AM | 显示全部楼层
感谢zhangyuwinnie分享~~~
回复 支持 反对

使用道具 举报

0

主题

0

精华

4

积分

新米人

Rank: 1

积分
4
发表于 1-12-2017 05:12 AM | 显示全部楼层
感谢zhangyuwinnie分享~~~
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表