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.
Solution 1: Brute Force + HashSet
Try all possible substrings
Time complexity: O(n^3)
Space complexity: O(n^2)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int distinctEchoSubstrings(string text) { const int n = text.length(); string_view t(text); unordered_set<string_view> s; for (int k = 1; k <= n / 2; ++k) for (int i = 0; i + k <= n; ++i) if (t.substr(i, k) == t.substr(i + k, k)) s.insert(t.substr(i, 2 * k)); return s.size(); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment