<分区>
我最近解决了 https://www.geeksforgeeks.org/find-given-string-can-represented-substring-iterating-substring-n-times/ 上提出的一个问题
问题是确定是否可以通过迭代子字符串 n 次从子字符串表示特定字符串。
例如字符串"abcabcabc"可以通过迭代子字符串"abc" 3来表示。
我想到了这个 Java 解决方案
public static boolean canForm (String str) {
if(str.isEmpty()||str.length()==1) return true;
int end;
if (str.length()%2==0) {
end = str.length()/2;
} else {
end = (str.length()-1)/2;
}
for (int i=1; i<=end; i++) {
String s = str.substring(0,i);
String compare = "";
while (compare.length()<str.length()) {
compare += s;
}
if (compare.equals(str)) return true;
}
return false;
}
问题的一个条件是解为 O(n)。我得出的结论是 O(n)，但我不确定我的解决方案是否真的是 O(n) 或者实际上是 O(n^2) 以及为什么。