求LeetCode 696计数二进制子串Java递归解法的时间复杂度

首先给出你提供的解法代码：

class Solution {
    public static int countBinarySubstrings(String s) {
        int res = 0;
        for(int i = 0; i < s.length()-1; i++) {
            if(s.charAt(i) != s.charAt(i+1)) 
                res += countValid(s, i, i+1);
        }
        return res;
    }
    
    public static int countValid(String s, int start, int end) {
        //base case
        if(start < 0 || end >= s.length()) 
            return 0;
        if(end-start == 1)
            return countValid(s, start-1, end+1) + 1;
        if(s.charAt(start+1) == s.charAt(start) && s.charAt(end-1) == s.charAt(end))
            return countValid(s, start-1, end+1) + 1;
        else
            return 0;
    }
}

时间复杂度结论 #

该解法的整体时间复杂度为O(n)，n为输入字符串的长度。

推导过程 #

• 外层循环遍历所有相邻字符对，基础开销为O(n)，仅当遇到相邻字符不同的分界点时才触发递归调用。
• 每个分界点的递归调用仅会向左右扩展，直到不满足相同字符规则或越界为止。所有递归调用的总次数不会超过n：任意一个字符最多只会被两次递归扩展访问（一次参与它和左侧相邻不同字符段的分界点计算，一次参与它和右侧相邻不同字符段的分界点计算），不存在多轮重复遍历同一个字符的情况。
• 两种极端场景验证：
  • 输入为000...000111...111：仅存在1个分界点，递归总调用次数为n/2，总操作数为n + n/2，量级为O(n)
  • 输入为010101...01：存在n-1个分界点，每个分界点的递归仅会调用1次就终止，总操作数为2*(n-1)，量级为O(n)

空间复杂度说明 #

你推导的最坏空间复杂度*O(n)*是正确的：最坏场景对应全0接全1的输入，递归深度为n/2，递归栈开销为O(n)。如果需要规避栈溢出风险，可以把递归扩展改为迭代写法，复杂度保持不变。

内容的提问来源于stack exchange，提问作者CrazyCSGuy