LeetCode – 459. Repeated Substring Pattern

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.)
这道题目我想了半天,后来用了一个取巧的办法:
  • double现在的string
  • 去掉头和尾巴(因为如果有substring,第一个肯定是substring的头部,最后一个肯定是他的尾部)
  • 然后看double的string是否包含老的string(如果重复老string至少有2个substring,新的至少4个,去除掉了头和尾,刚好剩下两个(如果原先三次,则新的会有4个),所以肯定包含)

public class Solution {
    public boolean repeatedSubstringPattern(String s) {
        if(s.length() <=1) return false;
        String s2 = s+s;
        s2 = s2.substring(1,s2.length()-1);
        if(!s2.contains(s)) return false;
        return true;
    }
}

喜欢的话订阅一个呗~第一时间收到文章更新哟~

发表评论

电子邮件地址不会被公开。