Given a string s, return whether it’s a repeating string.
Constraints
n ≤ 100,000 where n is the length of s
Example 1Input
s = “dogdogdog”
Output
trueExplanation
“dog” is repeated.Example 2
Input
s = “catdog”
Output
false
Repeated String Check in C++
The strategy is to partition the string into size 1, 2, 3 .. until n/2 where n is the size of the string. Also, we can skip the parition that n%j is not zero.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | bool solve(string s) { if (s.empty()) return false; for (int j = 1; (j <= s.size() / 2); ++ j) { if (s.size() % j != 0) continue; bool flag = true; for (int i = j; i < s.size(); ++ i) { if (s[i] != s[i - j]) { flag = false; break; } } if (flag) return true; } return false; } |
bool solve(string s) {
if (s.empty()) return false;
for (int j = 1; (j <= s.size() / 2); ++ j) {
if (s.size() % j != 0) continue;
bool flag = true;
for (int i = j; i < s.size(); ++ i) {
if (s[i] != s[i - j]) {
flag = false;
break;
}
}
if (flag) return true;
}
return false;
}Then, we can check the characters for equality of the neighbour parition. The time complexity is O(NM) where N is the number of characters in the string and M is the number of divisors for N.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
269 wordsloading...
Last Post: Convert a String to Camel Case Format in C++
Next Post: Math Algorithm to Count the Number of Palindromes Made From Letters
