Space Replacement

Question

• lintcode: (212) Space Replacement

  1. Write a method to replace all spaces in a string with %20.
     2. The string is given in a characters array, you can assume it has enough space
     3. for replacement and you are given the true length of the string.
     4. 5. Example
     5. Given "Mr John Smith", length = 13.
     6. 8. The string after replacement should be "Mr%20John%20Smith".
     7. 10. Note
     8. If you are using Java or Python，please use characters array instead of string.
     9. 13. Challenge
     10. Do it in-place.

題解

根據題意，給定的輸入陣列長度足夠長，將空格替換為%20 後也不會overflow。通常的思維為從前向後遍歷，遇到空格即將%20 插入到新陣列中，這種方法在生成新陣列時很直觀，但要求原地替換時就不方便了，這時可聯想到插入排序的做法——從後往前遍歷，空格處標記下就好了。由於不知道新陣列的長度，故首先需要遍歷一次原陣列，字符串類題中常用方法。
需要注意的是這個題並未說明多個空格如何處理，如果多個連續空格也當做一個空格時稍有不同。

Java

  1. public class Solution {
    2.     /**
    3.      * @param string: An array of Char
    4.      * @param length: The true length of the string
    5.      * @return: The true length of new string
    6.      */
    7.     public int replaceBlank(char[] string, int length) {
    8.         if (string == null) return 0;
    9.   10.         int space = 0;
    11.         for (char c : string) {
    12.             if (c == ' ') space++;
    13.         }
    14.   15.         int r = length + 2 * space - 1;
    16.         for (int i = length - 1; i >= 0; i--) {
    17.             if (string[i] != ' ') {
    18.                 string[r] = string[i];
    19.                 r--;
    20.             } else {
    21.                 string[r--] = '0';
    22.                 string[r--] = '2';
    23.                 string[r--] = '%';
    24.             }
    25.         }
    26.   27.         return length + 2 * space;
    28.     }
    29. }


  1. class Solution {
    2. public:
    3.     /**
    4.      * @param string: An array of Char
    5.      * @param length: The true length of the string
    6.      * @return: The true length of new string
    7.      */
    8.     int replaceBlank(char string[], int length) {
    9.         int space = 0;
    10.         for (int i = 0; i < length; i++) {
    11.             if (string[i] == ' ') space++;
    12.         }
    13.   14.         int r = length + 2 * space - 1;
    15.         for (int i = length - 1; i >= 0; i--) {
    16.             if (string[i] != ' ') {
    17.                 string[r] = string[i];
    18.                 r--;
    19.             } else {
    20.                 string[r--] = '0';
    21.                 string[r--] = '2';
    22.                 string[r--] = '%';
    23.             }
    24.         }
    25.   26.         return length + 2 * space;
    27.     }
    28. };

源碼分析

先遍歷一遍求得空格數，得到『新陣列』的實際長度，從後往前遍歷。

複雜度分析

遍歷兩次原陣列，時間複雜度近似為 O(n), 使用了r 作為標記，空間複雜度 O(1).