tags: Leetcode easy python c++ string Top 100 Liked Questions

459. Repeated Substring Pattern

[題目連結:] https://leetcode.com/problems/repeated-substring-pattern/description/

題目:

解題想法:

• 此題為判斷字串S，是否能由比他小的子字串構成

• 對於字串須知:

  • python
    • 字串*n= (字串)(字串)…n個
    • ex: abc*3=abcabcabc
  • C++:
    • 用累加

• 此題想法為:

  • 遍歷從頭到len(s)/2的所有距離i
  • 如果此距離i為len(s)的因子，表示有機會成為子字串
    • 將其position 0~i的子字串重複 len(s)/i次，判斷是否與s相等

Python:

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        #字串*n= (字串)(字串)....n個
        #abc*3=abcabcabc
        n=len(s)
        for i in range(1, n//2+1):#subStr長度為1至s的一半
            if n%i==0: #是倍數
                subStr=s[:i]
                if subStr*(n//i) == s:
                    return True
        return False

C++:

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n=s.size();
        for (int i=1; i<=n/2; i++){
            if (n%i==0){
                string subStr= "";
                //重複次數
                int time=n/i;
                for (int j=0; j<time; j++){
                    subStr += s.substr(0,i); //從頭數i個
                }
                if (subStr==s) return true;
            }
        }
        return false;
    }
};