题目如下:
Return the number of distinct non-empty substrings of
text
that can be written as the concatenation of some string with itself.Example 1:
Input: text = "abcabcabc" Output: 3 Explanation: The 3 substrings are "abcabc", "bcabca" and "cabcab".Example 2:
Input: text = "leetcodeleetcode" Output: 2 Explanation: The 2 substrings are "ee" and "leetcodeleetcode".Constraints:
1 <= text.length <= 2000
text
has only lowercase English letters.
解题思路:这个题目还真是奇葩,我一开始以为是找出符合 (xxx) * n 这样格式的子串,没想到却是(xxx) * 2格式,这个格式的意思就是,一个字符串分成前后两部分,两部分的值是一样的。因为text.length<=2000,所以直接暴力计算吧。
代码如下:
class Solution(object): def distinctEchoSubstrings(self, text): """ :type text: str :rtype: int """ res = 0 dic = {} # dp = [[0]* len(text) for _ in text] for i in range(len(text)): for j in range(i + 1, len(text)): if (j - i + 1) % 2 != 0: continue mid = (i+j) / 2 #print text[i:mid],text[mid:j+1] v1 = text[i:mid+1] v2 = text[mid+1:j+1] if v1 == v2 and v1 not in dic: #print v1,v2 res += 1 dic[v1] = 1 return res