Write a method to replace all spaces in a string with "%20". You may assume that the string has sufficient space at the end to hold the additional characters, and that you are given the "true" length of the string. (Note: If implementing in Java, please use a character array so that you can perform this operation in place.)
EXAMPLE
Input: "Mr John Smith ", 13
Output: "Mr%20John%20Smith"
Hint
- It's often easiest to modify strings by going from the end of the string to the beginning.
- You might find you need to know the number of spaces. Can you just count them?
Solution
习惯了Java的同学是不是和笔者一样，第一眼觉得为什么还有这种题？直接String.replaceAll就完了啊（手动滑稽）。原因是当有大量数据时，基于正则表达式的替换方法会产生大量开销，应当避免使用。根据题目中的提示，我们可以通过直接操作字符数组的方式来实现。
由于"%20"比单个空字符多出了2个字符，从左到右直接替换的话必然需要将数组中的字符多次整体右移。因此结合题目中字符尾部留有足够多空字符的条件，我们可以采用从右往左的倒插法进行计算。首先计算出字符串去掉尾部空字符后的真实长度len，以及字符串内包含的空字符个数count，那么替换后的长度即为len + count * 2，此处就是从右往左遍历的起点。下来便从len处从右往左遍历，每次遇到空字符串便插入"02%"，否则插入原字符。
public void URLify(char[] arr) {
if (arr == null) return;
int len = findLastCharacter(arr) + 1;
int count = 0;
for (int i = 0; i < len; i++) {
if (arr[i] == ' ') count++;
}
int index = len + count * 2;
for (int i = len - 1; i >= 0; i--) {
if (arr[i] == ' ') {
arr[index - 1] = '0';
arr[index - 2] = '2';
arr[index - 3] = '%';
index -= 3;
} else {
arr[index - 1] = arr[i];
index--;
}
}
}
private int findLastCharacter(char[] arr) {
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] != ' ') return i;
}
return -1;
}
