---
# System prepended metadata

title: \#459 Repeated Substring Pattern
tags: [leetcode, leetcode-easy, string]

---

# \#459 Repeated Substring Pattern
## *給定一字串s, 判斷s是否由某一子字串重複多次而組成*
## Log
 - build 20210829 by syhuang


## 神解
 - 令S1=S+S
 - 令S2 = S1去掉頭尾兩個字元
 - 當S出現在S2的時候就表示S符合題意
 - leetcode submit runtime 56%, memory 86%
```javascript=
var repeatedSubstringPattern = function(s) {
    if(s.length<2) return false;
    const s1 = s+s;
    const s2 = s1.substr(1,s1.length-2);
    return s2.indexOf(s) != -1;
};
```

## 初見2
 - 以初見為基礎, 改善迴圈裡的判斷條件:
     - 每次取tmpSubStr後, 抓下一個tmpSubStr出現的位置, 如果該位置是s.length的因數, 才有可能組成重複的子字串
 - 後續判斷同初見
 - leetcode submit runtime 5%, memory 41%
```javascript=
var repeatedSubstringPattern = function(s) {
    if(s.length < 2) return false;
    let tmpSubStr = '';
    let sLen = s.length;
    let result = false;
    for(let i=1; i<=sLen/2 && !result; i++){
        tmpSubStr = s.substr(0,i);
        let index = s.indexOf(tmpSubStr,i);
        if(index<0 || sLen%index != 0) continue;
        else if(s.replaceAll(tmpSubStr,'')!='') continue;
        else result = true;
    }
    return result;
};
```
## 初見
 - 跑迴圈紀錄每個可能的子字串, 並把原本的字串用子字串tmpSubStr來做取代成空字串, 如果取代後s變為空字串, 就表示符合題意
 - edge case s.length > 1
 - leetcode submit runtime 超過限制
```javascript=
var repeatedSubstringPattern = function(s) {
    if(s.length < 2) return false;
    let tmpSubStr = '';
    let result = false;
    for(i=0; i<s.length/2; i++){
        tmpSubStr = s.substr(0,i+1);
        if(s.replaceAll(tmpSubStr,'')==''){
            result = true;
            break;
        }
    }
    return result;
};
```
## 備註
## 參考
- [神解出處](https://leetcode.com/problems/repeated-substring-pattern/discuss/94334/Easy-python-solution-with-explaination)
###### tags: `leetcode`, `leetcode-easy`, `string`