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!