Fork me on GitHub

替换空格

发表于 | 分类于 
这是崔斯特的第一百一十一篇原创文章

努力、奋斗 (๑• . •๑)

替换空格

题目描述

请实现一个函数，将一个字符串中的每个空格替换成 %20。例如，当字符串为 We Are Happy，则经过替换之后的字符串为 We%20Are%20Happy。

思路

解法一

其实看到这道题，我最开始想到的就是字符串的replace方法，这显然不是面试官想要的答案，我就去看了下实现源码。

1
2
3
4
public String replace(CharSequence target, CharSequence replacement) {
    return Pattern.compile(target.toString(), Pattern.LITERAL).matcher(
            this).replaceAll(Matcher.quoteReplacement(replacement.toString()));
}

原来是用正则去匹配再替换的，再去看看正则替换的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public String replaceAll(String replacement) {
    reset();
    boolean result = find();
    if (result) {
        StringBuffer sb = new StringBuffer();
        do {
            appendReplacement(sb, replacement);
            result = find();
        } while (result);
        appendTail(sb);
        return sb.toString();
    }
    return text.toString();
}

发现用的是StringBuffer，保证线程安全。

解法二

好了，下面步入正题，创建 StringBuilder，遍历原字符串，遇到非空格，直接 append 到 StringBuilder 中，遇到空格则将 %20 append 到 StringBuilder 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public String replaceSpace(String str) {
        if (str == None || str.length() == 0) {
            return str;
        }
        StringBuilder sb = new StringBuilder();
        int len = str.length();
        for (int i = 0; i < len; ++i) {
            char ch = str.charAt(i);
            sb.append(ch == ' ' ? "%20" : ch);
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        String s = "We Are Happy";
        System.out.println(new Solution().replaceSpace(s));
    }
}

解法三（推荐）

先遍历原字符串，遇到空格，则在原字符串末尾 append 任意两个字符，如两个空格。

用指针 p 指向原字符串末尾，q 指向现字符串末尾，p, q 从后往前遍历，当 p 遇到空格，q 位置依次要 append ‘02%’，若不是空格，直接 append p 指向的字符。

🤔思路扩展
在合并两个数组（包括字符串）时，如果从前往后复制每个数字（或字符）需要重复移动数字（或字符）多次，那么我们可以考虑从后往前复制，这样就能减少移动的次数，从而提高效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    public String replaceSpace(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
        StringBuilder stringBuilder = new StringBuilder(str);
        int len = stringBuilder.length();
        StringBuilder strBuilder = new StringBuilder(stringBuilder);
        for (int i = 0; i < len; i++) {
            if (strBuilder.charAt(i) == ' ') {
                strBuilder.append("  ");
            }
        }
        int p = len - 1;
        int q = strBuilder.length() - 1;
        while (p > 0) {
            char ch = stringBuilder.charAt(p--);
            if (ch == ' ') {
                strBuilder.setCharAt(q--, '0');
                strBuilder.setCharAt(q--, '2');
                strBuilder.setCharAt(q--, '%');
            } else {
                strBuilder.setCharAt(q--, ch);
            }
        }
        return strBuilder.toString();
    }
    public static void main(String[] args) {
        String s = "We Are Happy";
        System.out.println(new Solution().replaceSpace(s));
    }
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def replace_space(self, s):
        if not isinstance(s, str) or len(s) <= 0 or s is None:
            return ''
        space_num = 0
        for i in s:
            if i == ' ':
                space_num += 1
        new_str_len = len(s) + space_num * 2
        new_str = new_str_len * [None]
        index_of_origin, index_of_new = len(s) - 1, new_str_len - 1
        while index_of_new >= 0 and index_of_origin <= index_of_new:
            if s[index_of_origin] == ' ':
                new_str[index_of_new - 2: index_of_new + 1] = ['%', '2', '0']
                index_of_new -= 3
            else:
                new_str[index_of_new] = s[index_of_origin]
                index_of_new -= 1
            index_of_origin -= 1
        return ''.join(new_str)
if __name__ == '__main__':
    s = Solution().replace_space('We Are Happy')
    print(s)

看着都头大