面试题 01.03. URL 化

题目描述

URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）

示例1:

 输入："Mr John Smith    ", 13
 输出："Mr%20John%20Smith"

示例2:

 输入："               ", 5
 输出："%20%20%20%20%20"

提示：

字符串长度在[0, 500000]范围内。

解法

方法一：使用 `replace()` 函数

思考

需要把前 $length$ 个字符中的空格换成 %20。题目给出的 $S$ 可能带有尾部填充，因此不能对整串做替换。

语言库的 replace 可在线性时间内完成子串替换。先截取 $S[:length]$，再将空格替换为 `%20$，即可同时处理有效前缀与填充。

该写法对齐 Python 的实现：一次切片加一次替换，时间与输出长度成正比。

直接利用 replace 将所有替换为 %20：

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串长度。

Python3TypeScriptRustJavaScriptSwift

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));
};

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
    }
}

方法二：模拟

思考

依赖库函数在面试中不够通用，其他语言未必提供同样的接口。

为此按有效前缀逐字符扫描：遇空格则写入 %20，否则写入原字符。结果缓冲的长度至多为原长的三倍，仍是线性扫描。

遍历字符串每个字符 $c$，遇到空格则将 %20 添加到结果中，否则添加 $c$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串长度。

Python3JavaGoRust

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()
    }
}

面试题 01.03. URL 化

题目描述

解法

方法一：使用 replace() 函数

方法二：模拟

评论

方法一：使用 `replace()` 函数