面试题4：替换空格

题目：

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

分析：

转换的规则是在‘%’后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII的码是32，即十六进制的0x20，因此空格被替换成“%20”。再比如‘#’的ASCII码为35，即十六进制的0x23，它在URL中被替换为“%23”。

有两种方式，一种是在原来的字符串上做替换，一种是创建新的字符串。这里我们假设是在原来的字符串上做替换。

解法一：从前往后替换

(a)

W

e

a

r

e

h

a

p

p

y

.

\0

(b)

W

e

%

2

0

a

r

e

h

a

p

p

y

.

\0

(c)

W

e

%

2

0

a

r

e

%

2

0

h

a

p

p

y

.

\0

假设字符串的长度是n。对每个空格字符，需要移动后面O(n)个字符，因此对含有O(n)个空格字符的字符串而言总的时间效率是O(n2)。


解法二：从后往前替换

(a)

W

e

a

r

e

h

a

p

p

y

.

\0

(b)

W

e

a

r

e

%

2

0

h

a

p

p

y

.

\0

(c)

W

e

%

2

0

a

r

e

%

2

0

h

a

p

p

y

.

\0

所有字符都只复制一次，因此这个算法的时间效率是O(n)。

代码：

/*length 为字符数组string的总容量*/
void ReplaceBlank(char string[], int length)
{
    if(string == NULL || length <= 0)
        return;
    /*originalLength 为字符串string的实际长度*/
    int originalLength = 0;
    int numberOfBlank = 0;
    while(string[i] != '\0')
    {
        ++ originalLength;
        if(string[i] == ' ')
            ++ numberOfBlank;
        ++ i;
    }
    /*newLength 为把空格替换成‘%20’之后的长度*/
    int newLength = originalLength + numberOfBlank * 2;
    if(newLength > length)
        return;
    int indexOfOriginal = originalLength;
    int indexOfNew = newLength;
    while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
    {
        if(string[indexOfOriginal] == ' ')
        {
            string[indexOfNew --] = '0';
            string[indexOfNew --] = '2';
            string[indexOfNew --] = '%';
        }
        else
        {
            string[indexOfNew --] = string[indexOfOriginal];
        }
        -- indexOfOriginal;
    }
}

package net.ecoolsoft.question;

public class WhiteSpaceReplace {
	/**
	 * 将字符数组中的空格替换成“%20”
	 * 模拟C++，认为数组长度足够
	 * @param input
	 */
	public void replaceWhiteSpace(char[] input) {
		if(input == null || input.length == 0) {
			return;
		}
		//遍历数组，查找空格个数
		int num = 0;
		int i = 0;
		for(i=0; i<input.length && input[i] != '\u0000'; i++) {
			if(input[i] == ' ') {
				++num;
			}
		}
		//两个指针，分别指向原字符数组末尾和新字符数组末尾
		int indexEnd = i-1;
		int indexNewEnd = indexEnd + num * 2;
		if(input.length < indexNewEnd+1) {
			return;
		}
		for(int j=indexEnd; j>=0; j--) {
			if(input[j] != ' ') {
				input[indexNewEnd--] = input[j];
			} else {
				input[indexNewEnd--] = '0';
				input[indexNewEnd--] = '2';
				input[indexNewEnd--] = '%';
			}
		}
		output(input);
	}
	
	/**
	 * 输出字符数组
	 * @param input
	 */
	public void output(char[] input) {
		System.out.println(input);	
	}
}

package net.ecoolsoft.question;

import junit.framework.Assert;

import org.junit.Test;

public class WhiteSpaceReplaceTest {
	
	@Test
	public void replaceWhiteSpaceTest() {
		String str = "Hello World, OK!";
		char[] result = replace(str);
		char[] expected = "Hello%20World,%20OK!".toCharArray();
		Assert.assertEquals(String.valueOf(expected).trim(), String.valueOf(result).trim());
	}
	
	@Test
	public void eplaceWhiteSpaceStartTest() {
		String str = " Hello World, OK! ";
		char[] result = replace(str);
		char[] expected = "%20Hello%20World,%20OK!%20".toCharArray();
		Assert.assertEquals(String.valueOf(expected).trim(), String.valueOf(result).trim());
	}
	
	@Test
	public void eplaceWhiteSpaceAllSpaceTest() {
		String str = "     ";
		char[] result = replace(str);
		char[] expected = "%20%20%20%20%20".toCharArray();
		Assert.assertEquals(String.valueOf(expected).trim(), String.valueOf(result).trim());
	}
	
	@Test
	public void eplaceWhiteSpaceNotEnough() {
		String str = "Hello World, OK!";
		char[] input = str.toCharArray();
		WhiteSpaceReplace wsr = new WhiteSpaceReplace();
		wsr.replaceWhiteSpace(input);
		char[] expected = input;
		Assert.assertEquals(expected, input);
	}
	
	@Test
	public void eplaceWhiteSpaceNullTest() {
		String str = null;
		char[] result = replace(str);
		char[] expected = null;
		Assert.assertEquals(expected, result);
	}
	
	private char[] replace(String str) {
		char[] input = null;
		if(str != null) {
			input = new char[str.length()*3];
			for(int i=0; i<str.length(); i++) {
				input[i] = str.charAt(i);
			}
		}
		WhiteSpaceReplace wsr = new WhiteSpaceReplace();
		wsr.replaceWhiteSpace(input);
		return input;
	}
}

参考资料：《剑指Offer——名企面试官精讲典型编程题》