Interview Problem: String Replacement.

Problem:

Replace all spaces in a string with '%20'.

Solution:

Go through every characters in the string, then replace it with %20 once the character is space.
Time complexity: O(n).
Space complexity: O(n).

/**
 * replace all spaces in a string with '%20'
 */

/**
 * @author antonio081014
 * @since Nov 5, 2011, 9:20:12 PM
 */
public class StringReplace {

    public String replaceSpace(String s) {
        String tmp = "";
        for (int i = 0; i < s.length(); i++)
            if (s.charAt(i) == ' ')
                tmp += "%20";
            else
                tmp += s.charAt(i);
        return tmp;
    }
}

Testing:

1st, using string having space.
2nd, using string without space.

PS: The following solution is wrong, though the idea is quite right, which could save much memory while spending the similar amount of time. The reason for its failure is it would rise IndexOutOfBoundsException exception caused by line: str[newLength] = '\0';The newLength will be equal to or bigger than the original length, the memeory could not be accessed until it's allocated before. Here if newLength is larger than the original one, the program will try to access the memory which is not allocated or we could say that the memory is not assigned to the program by the virtual system.
/**
 * replace all spaces in a string with '%20'
 */
/**
 * @author antonio081014
 * @since Nov 5, 2011, 9:20:12 PM
 */
public class StringReplace {

    public static void ReplaceFun(char[] str, int length) {
        int spaceCount = 0, newLength, i = 0;
        for (i = 0; i < length; i++) {
            if (str[i] == ' ') {
                spaceCount++;
            }
        }
        newLength = length + spaceCount * 2;
        str[newLength] = '\0';
        for (i = length - 1; i >= 0; i--) {
            if (str[i] == ' ') {
                str[newLength - 1] = '0';
                str[newLength - 2] = '2';
                str[newLength - 3] = '%';
                newLength = newLength - 3;
            } else {
                str[newLength - 1] = str[i];
                newLength = newLength - 1;
            }
        }
    }
}