StringBuilder空间复杂度问询：输入字符串及仅追加元音时的复杂度判定

Great question! Let's walk through both scenarios clearly:

1. 原代码的空间复杂度 #

First, let's restate the code we're analyzing:

String s = "dfgdfgdfga"; 
StringBuilder sb = new StringBuilder(); 
for (int i = 0;i < s.length(); i++) { 
    sb.append(s.charAt(i)); 
} 
return sb.toString();

The space complexity here is O(n) (where n is the length of input string s).

Here's why: The StringBuilder ends up storing every single character from s—so its memory usage scales directly with the length of the input. When we talk about space complexity, we're usually referring to additional space (beyond what the input itself uses), and since sb grows linearly with n, this falls into the O(n) category.

2. 仅追加元音字符的空间复杂度 #

If you modify the code to only append vowels to the StringBuilder, the space complexity is still O(n)—but this is based on the worst-case scenario, which is the standard for most complexity analysis:

• Imagine the input string is entirely made up of vowels (like s = "aeiouaeiou..."). In this case, the StringBuilder will still store all n characters, so its memory usage is linear with n.
• Sure, in the best case (no vowels in s), the space used would be O(1), but we always default to the worst case when stating time/space complexity unless specified otherwise.

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