英文:
What is the runtime & space complexity of this Repeated Substring Pattern code? (Code is written in Java)
问题
public boolean repeatedSubstringPattern(String s) {
if (s == null || s.isEmpty()) return true;
int l = s.length();
for (int i = l / 2; i > 0; --i) {
if (l % i == 0 && isThisSubString(s, s.substring(0, i), l / i)) {
return true;
}
}
return false;
}
private boolean isThisSubString(String s, String subString, int m) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < m; ++i) {
sb.append(subString);
}
return s.equals(sb.toString());
}
}
英文:
I wrote this solution for LeetCode #459 problem. https://leetcode.com/problems/repeated-substring-pattern/
I want to know the runtime & space complexity of this solution.
I'm assuming runtime complexity of O(logN N) where N is the length of the String. Am I right?
public boolean repeatedSubstringPattern(String s) {
if (s == null || s.isEmpty()) return true;
int l = s.length();
for (int i = l / 2; i > 0; --i) {
if (l % i == 0 && isThisSubString(s, s.substring(0, i), l / i)) {
return true;
}
}
return false;
}
private boolean isThisSubString(String s, String subString, int m) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < m; ++i) {
sb.append(subString);
}
return s.equals(sb.toString());
}
}
答案1
得分: 0
在最坏的情况下，当 i 等于 1 时，m 等于 5。isThisSubString 方法将遍历整个字符串。因此在最坏的情况下，渐近复杂度为 O(n^2)。
英文:
In the worst case when i is 1, m is equal to 5. isThisSubString method will be iterating over the entire string. So Asymptotically in the worst case, it is O(n^2).
专注分享java语言的经验与见解，让所有开发者获益！
评论