【剑指offer】面试题5：替换空格

Dear 丶 2022-04-01 12:16 215阅读 0赞

> **题目：请实现一个函数，把字符串中的每个空格替换成 “%20”。 例如输入 “We are happy.”，则输出”We%20are%20happy.”。**

*  ###  时间复杂度为O(**![n^\{2\}][n_2]**)的解法 ###

最直观的做法就是从头到尾扫描字符串，每次碰到空格字符的时候就进行替换。由于是把1个字符替换成3个字符，因此必须把空格后面的所有字符都要后移2个字节，否则就会有两个字符被覆盖了。

假设字符串的长度是n，对每个空格字符，需要移动后面O(n)个字符，因此对于含有O(n)个空格字符的字符串而言，总的时间效率是O(**![n^\{2\}][n_2]**)。

public class BlankReplace {
    
    	public static String replaceBlank(String input){
    		if(input == null){
    			return null;
    		}
    		
    		StringBuffer outputBuffer = new StringBuffer();
    		for (int i = 0; i < input.length(); i++) {
    			if(input.charAt(i) == ' '){				
    				outputBuffer.append("%");
    				outputBuffer.append("2");
    				outputBuffer.append("0");
    			}else{
    				outputBuffer.append(String.valueOf(input.charAt(i)));
    			}	
    		}
    		return new String(outputBuffer);
    	}
    	
    	public static void main(String[] args) {
    		String a = "We are happy.";
    		System.out.println(replaceBlank(a));
    	}
    }

上面的思路是：从前往后扫描，下面我们改变下思路，从后往前扫描。

*  ## 时间复杂度为O(n)的解法 ##

我们可以先遍历一次字符串，这样就能够统计出字符串中的空格总数，则就可以计算出替换之后的字符串的总长度。每替换一个空格，长度增加2，因此替换以后字符串的长度等于原来的长度加上2乘以空格数目。

我们从字符串的后面开始复制和替换，首先准备两个指针，P1和P2，P1指向原始字符串的末尾，而P2指向替换之后的字符串的末尾。

接下来我们向前移动指针P1，逐个把它指向的字符复制到P2指向的位置，直到碰到空格为止。碰到空格后，把P1向前移动1格，在P2之前插入字符串”%20“，由于”%20“的长度为3，同时也要把P2向前移动3格。后面每次遇到空格后都这样做，直到P1和P2指向同一个位置，表明所有的空格已经替换完毕。

这种从后外向前的替换过程，所有的字符串只复制（移动）一次，因此这个算法的时间效率是O(n)。代码如下：

public class replaceSpace {
    
    	public static void replaceSpace(String str){
    		if(str == null || str.length() <= 0){
    			throw new IllegalArgumentException("输入的参数有问题");
    		}
    		
    		// 字符串的初始长度
    		int length = str.length();
    		// 字符串替换后的长度
    		int newLength = str.length() + getBlankNum(str) * 2;
    		
    		char[] tempArr = new char[newLength];
    		// 将str复制到新的 tempArr 数组中
    		System.arraycopy(str.toCharArray(), 0, tempArr, 0, str.toCharArray().length);
    		int indexOfOriginal = length - 1;
    		int indexOfNew = newLength - 1;
    		System.out.println("未替换空格时的字符串:");
    		printArray(str.toCharArray());
    		
    		while(indexOfOriginal >= 0 && indexOfOriginal != indexOfNew){
    			if(tempArr[indexOfOriginal] == ' '){
    				tempArr[indexOfNew--] = '0';
    				tempArr[indexOfNew--] = '2';
    				tempArr[indexOfNew--] = '%';
    			}else{
    				tempArr[indexOfNew--] = tempArr[indexOfOriginal];
    			}
    			indexOfOriginal--;  // 从后先前遍历
    		}
    		
    		System.out.println("替换后的字符串为：");
    		printArray(tempArr);
    	}
    
    	// 获取空格数
    	private static int getBlankNum(String str) {
    		int count = 0;   // 空格数 
    		for (int i = 0; i < str.length(); i++) {
    			// 获取str中下标为i的元素，判断它是否为空格
    			String tempStr = String.valueOf(str.charAt(i));
    			if(tempStr.equals(" ")){
    				count++;
    			}
    		}
    		return count;
    	}
    	
    	// 打印char[]数组
    	public static void printArray(char[] arr){
    		for(char i : arr){
    			System.out.print(i);
    		}
    		System.out.println();
    	}
    	
    	// 测试
    	public static void main(String[] args) {
    		String str = "We are happy";
    		replaceSpace(str);
    	}
    }

运行结果：

![20181230215824721.png][]

[n_2]: https://private.codecogs.com/gif.latex?n%5E%7B2%7D
[20181230215824721.png]: /images/20220401/0131d1e1bb0e47678fa69bf076b67e40.png