Skip to content

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

Thinking

Spaces in the first \(length\) characters must become %20. \(S\) may contain trailing padding, so a replace on the whole string is wrong.

A library replace finishes the substitution in linear time. Slice \(S[:length]\) first, then replace spaces, which handles both the live prefix and the padding.

That matches the Python code: one slice and one replace, linear in the output length.

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.

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

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

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

1
2
3
4
5
6
7
8
/**
 * @param {string} S
 * @param {number} length
 * @return {string}
 */
var replaceSpaces = function (S, length) {
    return encodeURI(S.substring(0, length));
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    func replaceSpaces(_ S: String, _ length: Int) -> String {
        let substring = S.prefix(length)
        var result = ""

        for character in substring {
            if character == " " {
                result += "%20"
            } else {
                result.append(character)
            }
        }

        return result
    }
}

Solution 2: Simulation

Thinking

A library helper is not portable across languages that the problem may be solved in.

Scan the valid prefix character by character: write %20 for a space and the original character otherwise. The buffer is at most three times as long, still a linear pass.

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.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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:])
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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()
    }
}

Comments