面试题 01.03

Write a method to replace all spaces in a string with '%20'. You may assume that the string has sufficient space at the end to hold the additional characters,and that you are given the "true" length of the string. (Note: If implementing in Java,please use a character array so that you can perform this operation in place.)

Example 1:

Input: "Mr John Smith ", 13 Output: "Mr%20John%20Smith" Explanation: The missing numbers are [5,6,8,...], hence the third missing number is 8. Example 2:

Input: " ", 5 Output: "%20%20%20%20%20"

Note:

0 <= S.length <= 500000

Solutions

1. straight forward

class Solution {
public:
    string replaceSpaces(string S, int length) {
        int len = 0;
        for (int i = 0; i < length; i++)
            len += S[i] == ' ' ? 3 : 1;
        int r = length - 1, w = len - 1;
        while (r >= 0) {
            if (S[r] == ' ') {
                S[w--] = '0';
                S[w--] = '2';
                S[w--] = '%';
            }
            else
                S[w--] = S[r];
            r--;
        }

        return S.substr(0, len);
    }
};