What is the best approach for time & space complexity for string word reversal

Question

What should be the best approach when it comes to time & space complexity? Approach 1 or 2?

Approach 1:

Stack<Character> st = new Stack<Character>();
for (int i = 0; i < str.length(); ++i) {
    if (str.charAt(i) != ' ')
        st.push(str.charAt(i));
    else {
        while (st.empty() == false) {
            System.out.print(st.pop());
        }
        System.out.print(" ");
    }
}
while (st.empty() == false) {
    System.out.print(st.pop());
}

Approach 2:

String welcomeString = "Welcome to Zscaler";
String removeSpace[] = welcomeString.split(" ");
String reversedString = "";
for (int i = 0; i < removeSpace.length; i++) {
    String getString = removeSpace[i];
    reversedString = "";
    for (int j = getString.length() - 1; j >= 0; j--) {
        reversedString = reversedString + getString.charAt(j);
    }
    System.out.print(reversedString + " ");
}

score 0 · Accepted Answer · answered Oct 04 '22 at 09:36

Space complexity are the same for both.

In the second approach, you have the removeSpace array, which seems like it duplicates the whole string, but internally it just contains substrings of the original string, which does not duplicate anything.

For time complexity, it depends on the compiler. Appending characters one at a time to strings (in approach 2) can be expensive, since it could allocate new String objects everytime. The compiler may be smart enough in this case to optimize that.

Better to use StringBuilder in approach 2, then the time complexity will be the same for both, I think.

See also How many string additions do you need for a StringBuilder to be more efficient?

What is the best approach for time & space complexity for string word reversal

1 Answers1