459. Repeated Substring Pattern

Level : Easy

原題連結 : Click

題目 :

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

Example :

解題思路 :

• 這題也是屬於KMP演算法的應用，需要你找出該字串是否全部是由單一子字串構築而成
• 這時候使用KMP中的next table就很好解決，可以藉由next table中值的變化看出其是否規律的由單一子字串組合而成
• 假設有一字串abcabcabcabc，他的next table會像是000123456789
• 也就是說總長度扣掉不為0的長度就可以得到為0的長度，他也恰恰是我們所需要最小單元子字串長度
• 那如何斷定他是否為同一子字串組成呢? 可以將next table最後一個值去 mod 最小單元子字串長度
• 若結果為0(得以整除)，也就是說他剛好是由其子字串組成

以下是我的解法 - time complexity: O(n) , space complexity: O(n)

Runtime: 0 ms, faster than 100.00% of Go online submissions for Repeated Substring Pattern.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func repeatedSubstringPattern(s string) bool {
    
    length := len(s)
    
    if length == 0 {
        return false
    }
    
    next := make([]int, len(s))

    j := 0
    
    for i := 1; i < length; i++ {
        

        
        for j > 0 && s[i] != s[j] {
            j = next[j-1]
        }
        
        if s[i] == s[j] {
            j++
        }
        
        next[i] = j
        
    }
    return next[length-1] != 0 && length % (length - next[length-1]) == 0
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!