LeetCode Js-459. Repeated Substring Pattern

    LeetCode Js-String

    Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

    給定一個字串 s,檢查是否可以透過取得它的子字串,並確認子字串的多個副本附加在一起來可以建構它。
    

    Example 1:

    Input: s = "abab"
    Output: true
    

    Example 2:

    Input: s = "aba"
    Output: false
    

    Example 3:

    Input: s = "abcabcabcabc"
    Output: true
    

    solution:
    首先思考 s 字串是否可以組成多重個 sub s字串所需要的條件,
    從總長度、最長的子字串長度為總長度的一半、總長度下的子字串會有幾組,
    接著透過找出最短結果的字串來進行遍歷,
    並依序比對得到結果。

    Code 1: BigO(n^2)

    var repeatedSubstringPattern = function(s) {
        // appending multiple copies of the substring
        // 1.0 s 為 多個 sub s 組成。
        const n = s.length; //4
    
        // 1.1 sub s 最多的長度為 s / 2。
        for (let i = 1; i <= n / 2; i++){ //2
            // 1.2 sub s 會有幾組? (n % i === 0) ex. 8 % 2 === 0
            if (n % i === 0) {
                const substring = s.slice(0, i);
                let repeated = ""
                // 1.3 透過遍歷找出符合的 sub s。
                for (let j = 0; j < n / i; j++) {
                    repeated += substring; //aaaa, abab
                }
                if (repeated === s) return true;
            }
        }
        return false;
    };
    

    FlowChart:
    Example 1

    a
    aa
    aaa
    aaaa
    ab
    abab
    input: (s = "abab") output: true // Excellent!
    

    Example 2

    a
    aa
    aaa
    input: (s = "aba") output: false // Excellent!
    

    Example 3

    a
    aa
    aaa
    aaaa
    aaaaa
    aaaaaa
    aaaaaaa
    aaaaaaaa
    aaaaaaaaa
    aaaaaaaaaa
    aaaaaaaaaaa
    aaaaaaaaaaaa
    ab
    abab
    ababab
    abababab
    ababababab
    abababababab
    abc
    abcabc
    abcabcabc
    abcabcabcabc
    input: (s = "abcabcabcabc") output: true // Excellent!