Contents

[Golang][Leetcode][String]刷題系列-459-KMP Algorithm


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 :

Note

Input: s = “abab”

Output: true

Explanation: It is the substring “ab” twice.


Input: s = “aba”

Output: false


Input: s = “abcabcabcabc”

Output: true

Explanation: It is the substring “abc” four times or the substring “abcabc” twice.


解題思路 :

  • 這題也是屬於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” 我們峰頂見!!!