Repeated Substring Pattern

Leave a comment

February 13, 2017 by oneOokay

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:

Input: "abab"

Output: True

Explanation: It's the substring "ab" twice.

Example 2:

Input: "aba"

Output: False

Example 3:

Input: "abcabcabcabc"

Output: True

Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

Easy 但是没写出来.

除掉KMP以外基本两种想法:

  1. 先确定repeat的substring
  2. 先确定repeat的次数

我尝试了1,但是没有跑过.大部分的解法是通过2实现的.其实1和2是相辅相成的正反两面,一个想不通的时候不妨从反面想想看.

这题就没有什么其他的点了.

public boolean repeatedSubstringPattern(String str) {
        if (str == null || str.length() <= 1) return false;
        int length = str.length();
        for (int repeat = 2; repeat <= length; repeat ++){
            if (length % repeat != 0) continue;
            if (check(str, repeat)) return true;
        }
        return false;
    }
    
    public boolean check(String str, int repeat){
        int len = str.length() / repeat;
        String subStr = str.substring(0, len);
        for (int i = 0; i < str.length(); i ++){
            if (str.charAt(i) != subStr.charAt(i % len)) return false;
        }
        return true;
    }

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: