问题描述

题目描述
请实现一个函数,把字符串中的每个空格替换成“%20”

要求
时间限制:1秒
空间限制:32768K

方法原型

public void replaceSpace(char[] str)

输入输出例子
输入:“Wa are happy” 输出:“We%20are%20happy”

解题思路

此题最自然的思路,就是从字符串的开始遍历,寻找空格,当遇到空格时,就将空格替换为"%20",因为%20占3个字符,空格占一个字符,因此空格后的所有字符需要整体后移。
此思路示意如以下动图:

但是不难发现,以上解法过程中,有一部分字符被移动了多次(如happy),这使得该算法的时间复杂度为\(O(n^2)\),当字符串较长,空格较多时,很容易超时。
为了尽量降低时间复杂度,我们可以对遍历、替换的策略进行改进:

  • 先遍历一遍字符串,获取空格的总数目
  • 知道空格的总数目后,就可以知道替换空格为"%20"所需的额外空间,进而知道【替换后的】字符串的结尾坐标
  • 从尾部开始遍历待替换的字符串,遇到空格后:将空格后至尾部的所有字符整体移动到尾部,并紧挨其填充%20
  • 更新尾部的位置

以上算法如下图所示:

这种解法的时间复杂度为\(O(n)\),空间复杂度为\(O(1)\)

相关代码

我们给出后一种思路的JAVA版本的实现。

package com.shellmad;

public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        char[] str = {'W', 'e', ' ', 'a', 'r', 'e', ' ', 'h', 'a', 'p', 'p', ' ', '\0'};
        solution.replaceSpace(str);
        System.out.println(str);
    }

    public void replaceSpace(char[] str) {

        // 检查输入
        if (str == null || str.length == 0) {
            return;
        }

        /*
            统计空格的个数
            获得源字符串终点下标
            获得替换空格后的字符串的终点下标
         */
        int srcEnd = 0;
        int destEnd = 0;
        int spaceCount = 0;

        while (str[srcEnd] != '\0' && srcEnd < str.length - 1) {
            if (str[srcEnd] == ' ') {
                spaceCount++;
            }
            srcEnd++;
        }
        srcEnd--;
        destEnd = spaceCount * 2 + srcEnd;

        if (spaceCount == 0 || destEnd >= str.length) {
            return;
        }

        // 替换空格
        while (srcEnd >= 0) {

            if (str[srcEnd] == ' ') {
                str[destEnd--] = '0';
                str[destEnd--] = '2';
                str[destEnd--] = '%';

            } else {
                str[destEnd--] = str[srcEnd];
            }

            srcEnd--;
        }
    }
}
02-10 02:08