Repeated Substring Pattern

Leave a comment

November 26, 2016 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.)

我的想法是用anagram的想法来做:

  1. 首先符合条件的substring的length一定是<= str length的
  2. 从i = 1开始表示从index=0 到i的string的substring,符合条件的substring那么该string是一个以substring为单个元素的anagram
  3. 接着对string进行anagram的判定
public class Solution {
    public boolean repeatedSubstringPattern(String str) {
        int i = 1;
        while (i <= str.length() / 2){
            if (str.length() % i == 0){//很重要的一个提高效率的一步
                String subStr = str.substring(0, i);
                if (isAnagram(str, subStr)){
                    return true;
                }
            }
            i ++;
        }
        return false;
    }
    
    private boolean isAnagram(String str, String subStr){
        int m = str.length();
        int n = subStr.length();
        int start = 0;
        int end = m - n;
        while (start <= end){
             if (end - start >= n){//如果end和start相差大于n,那么start和end
不会重合,需要对end和start进行判断
                if (!str.substring(start, start + n).equals(subStr) || 
                !str.substring(end, end + n).equals(subStr)){
                    return false;
                }    
            }else if (end == start){//如果end和start相等:那么说明是一个奇数的
anagram
                if (!str.substring(start, start + n).equals(subStr)){
                    return false;
                }
            }else {//如果end - start < n说明不是anagram直接跳出。
                return false;
            }
            start += n;
            end -= n;
        }
        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: