[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.)

重复的子字符串。

题意很好理解，给一个字符串，请问这个字符串是否是一个子串拼接成的。这个题的思想不涉及算法。既然是判断这个字符串是否是由一个较小的子串拼接而成的，如果input字符串的长度小于2，则一定是错的。接着如何找子串呢？首先，这个子串的长度应该是介于1 - s.length() / 2之间，然后需要用substring一点点去截取一个temp string，判断这个temp string是否能整除字符串的总长，如果不是，则这个temp string就不是一个符合题意的子串。如果是，则试着用这个temp string拼接M次，看看最后拼接的结果是否和input字符相同。

时间O(n^2)

空间O(n)

Java实现

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        // corner case
        if (s.length() < 2) {
            return false;
        }

        // normal case
        int len = s.length();
        for (int i = len / 2; i >= 1; i--) {
            if (len % i == 0) {
                // 有m个长度为i的substring
                int m = len / i;
                String sub = s.substring(0, i);
                StringBuilder sb = new StringBuilder();
                // 用m个substring i拼成一个长的string 再和s比较
                for (int j = 0; j < m; j++) {
                    sb.append(sub);
                }
                if (sb.toString().equals(s)) {
                    return true;
                }
            }
        }
        return false;
    }
}

JavaScript实现

/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function (s) {
    // corner case
    if (s.length < 2) {
        return false;
    }

    // normal case
    let len = s.length;
    for (let i = Math.floor(len / 2); i >= 1; i--) {
        if (len % i == 0) {
            let temp = '';
            let m = Math.floor(len / i);
            for (let j = 0; j < m; j++) {
                temp += s.substring(0, i);
            }
            if (temp === s) {
                return true;
            }
        }
    }
    return false;
};

相关题目

459. Repeated Substring Pattern

686. Repeated String Match

LeetCode 题目总结