Question

01.03. String to URL

中文文档

Description

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:

1. 0 <= S.length <= 500000

Solutions

Solution 1: Using replace() function

Directly use replace to replace all with %20:

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string.

class Solution:
  def replaceSpaces(self, S: str, length: int) -> str:
    return S[:length].replace(' ', '%20')

function replaceSpaces(S: string, length: number): string {
  return S.slice(0, length).replace(/\s/g, '%20');
}

impl Solution {
  pub fn replace_spaces(s: String, length: i32) -> String {
    s[..length as usize].replace(' ', "%20")
  }
}

/**
 * @param {string} S
 * @param {number} length
 * @return {string}
 */
var replaceSpaces = function (S, length) {
  return encodeURI(S.substring(0, length));
};

Solution 2: Simulation

Traverse each character $c$ in the string. When encountering a space, add %20 to the result, otherwise add $c$.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string.

class Solution:
  def replaceSpaces(self, S: str, length: int) -> str:
    return ''.join(['%20' if c == ' ' else c for c in S[:length]])

class Solution {
  public String replaceSpaces(String S, int length) {
    char[] cs = S.toCharArray();
    int j = cs.length;
    for (int i = length - 1; i >= 0; --i) {
      if (cs[i] == ' ') {
        cs[--j] = '0';
        cs[--j] = '2';
        cs[--j] = '%';
      } else {
        cs[--j] = cs[i];
      }
    }
    return new String(cs, j, cs.length - j);
  }
}

func replaceSpaces(S string, length int) string {
  // return url.PathEscape(S[:length])
  j := len(S)
  b := []byte(S)
  for i := length - 1; i >= 0; i-- {
    if b[i] == ' ' {
      b[j-1] = '0'
      b[j-2] = '2'
      b[j-3] = '%'
      j -= 3
    } else {
      b[j-1] = b[i]
      j--
    }
  }
  return string(b[j:])
}

impl Solution {
  pub fn replace_spaces(s: String, length: i32) -> String {
    s.chars()
      .take(length as usize)
      .map(|c| {
        if c == ' ' { "%20".to_string() } else { c.to_string() }
      })
      .collect()
  }
}