C#LeetCode刷题之#459-重复的子字符串（Repeated Substring Pattern）

问题

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

输入: “abab”

输出: True

解释: 可由子字符串 “ab” 重复两次构成。

输入: “aba”

输出: False

输入: “abcabcabcabc”

输出: True

解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

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.

Input: “abab”

Output: True

Explanation: It’s the substring “ab” twice.

Input: “aba”

Output: False

Input: “abcabcabcabc”

Output: True

Explanation: It’s the substring “abc” four times. (And the substring “abcabc” twice.)

示例

public class Program {

    public static void Main(string[] args) {
        var s = "Iori's Blog";

        var res = RepeatedSubstringPattern(s);
        Console.WriteLine(res);

        s = "abaababaab";

        res = RepeatedSubstringPattern2(s);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static bool RepeatedSubstringPattern(string s) {
        //LeetCode 超出内存限制，未AC
        //基本思路是一个指针截断字符串
        //指针前所有的字符串为子字符串参考计算
        //往后循环看每一段是否相同
        //如果每一段都相同，则满足题意
        for(var i = 0; i < s.Length / 2; i++) {
            var sub = s.Substring(0, i + 1);
            if(s.Length % sub.Length != 0) continue;
            var nums = s.Length / sub.Length;
            for(var j = 1; j < nums; j++) {
                if(s.Substring(j * sub.Length, sub.Length) != sub) break;
                if(j == nums - 1) return true;
            }
        }
        return false;
    }

    private static bool RepeatedSubstringPattern2(string s) {
        //基本思路是一个指针截断字符串
        //指针前所有的字符串为子字符串参考计算
        //以此字符串循环构建新字符
        //比较新构建的字符串是否和原串相同
        //变量 repeat 不能使用字符串，否则效率较低
        //LeetCode 会TLE超时无法AC
        var length = s.Length;
        for(var i = length / 2; i >= 1; i--) {
            if(length % i == 0) {
                var repeat = new StringBuilder();
                for(var j = 0; j < length / i; j++) {
                    repeat.Append(s.Substring(0, i));
                }
                if(repeat.ToString() == s) return true;
            }
        }
        return false;
    }

}

以上给出2种算法实现，以下是这个案例的输出结果：

False
True

分析：

显而易见，以上2种算法的时间复杂度均为：  。