Oliver's Blog

剑指Offer 面试题04：替换空格

  • Jun 01, 2012

替换空格

题目描述

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

解题思路

先遍历一次字符串，得到替换后的字符串总长度。以替换后的字符串总长度新建一个字符数组，再次遍历字符串，把每个字符复制到新字符数组中，遇到空格则替换为%20

原书题目使用C语言，传入参数是足够大的字符数组，在不允许创建新的字符数组的情况下，假如从左到右遍历字符数组并替换，则会导致后面的字符多次移位。更好的解法是先遍历一次字符串，计算得到替换后的字符串总长度。注意C语言的字符串是以特殊字符\0作为终结符的。然后使用两个指针，都指向原来传入的字符数组，但位置不同。一个指向替换后的字符串结尾位置，一个指向原字符串的结尾位置。然后开始逐一复制字符，遇到空格则替换为%20

代码

public class Solution {
    public String replaceSpace(StringBuffer str) {
    	if (str != null) {
            int strLength = str.length();
            int finalStrLength = strLength;
            
            // 遍历一次字符串，得到替换后的字符串总长度
            for (int i = 0; i < strLength; i++) {
                char c = str.charAt(i);
                if (c == ' ') {
                    finalStrLength += 2;
                }
            }
            
            if (finalStrLength == strLength) {
                return str.toString();
            } else {
                // 再次遍历字符串，把每个字符复制到新字符数组中，遇到空格则替换为%20
                char[] resultCharArray = new char[finalStrLength];
                for (int i = strLength - 1, j = finalStrLength - 1; i >=0; i--) {
                    char c = str.charAt(i);
                    if (c != ' ') {
                        resultCharArray[j] = c;
                        j--;
                    } else {
                        resultCharArray[j] = '0';
                        j--;
                        resultCharArray[j] = '2';
                        j--;
                        resultCharArray[j] = '%';
                        j--;
                    }
                }
                return new String(resultCharArray);
            }
        } else {
            return null;
        }
    }
}
Search