我编写了一段代码来递归地从字符串中删除相邻的重复项
class Solution{
String rremove(String s) {
// code here
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < s.length()) {
char currentChar = s.charAt(i);
int j = i + 1;
// Find the index of the next different character
while (j < s.length() && s.charAt(j) == currentChar) {
j++;
}
// If adjacent duplicates found, skip them
if (j - i > 1) {
i = j;
} else {
sb.append(currentChar);
i++;
}
}
String result = sb.toString();
// If result string is different from original, recursively call the function
if (!result.equals(s)) {
return rremove(result);
}
return result;
}
现在,我想了解这段代码的时间复杂度,因为这里的递归调用次数不是固定的,因此在查看代码时感到非常困惑。虽然,每个方法调用都是O(n),但是随着递归的深度,它变得不确定。因此,请帮助我了解此代码的最佳情况和最坏情况。
代码来自 GFG,标题为“递归删除所有相邻重复项”
如果我们从分析中排除递归调用,复杂度确实是 O(𝑛)。这也是时间复杂度最好的情况,即由于输入中不存在相邻重复而未进行递归调用时。
当我们合并递归调用时,最坏的情况会发生在回文数中,唯一的重复字符出现在中心。例如
abababababbababababa
。现在我们调用 rremove
,得到长度为 𝑛 的字符串,然后是 𝑛−2, 𝑛−4, ... 2, 0.
所以最坏情况的时间复杂度是 O(𝑛²)。