Space Replacement

Question

  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.
  5. Example
  6. Given "Mr John Smith", length = 13.
  8. The string after replacement should be "Mr%20John%20Smith".
  10. Note
  11. If you are using Java or Python，please use characters array instead of string.
  13. Challenge
  14. 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;
  10.         int space = 0;
  11.         for (char c : string) {
  12.             if (c == ' ') space++;
  13.         }
  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.         }
  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.         }
  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.         }
  26.         return length + 2 * space;
  27.     }
  28. };

源碼分析

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

複雜度分析

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