/*
 * Write a method to replace all spaces in a string with '%20'.
 * You may assume that the string has sufficient space at the end
 * of the string 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.)
 *
 * CC150 1.4 Replace Space
 * @author: Scarlett Chen
 * @Date: 12/20/2014  Sat 9:28 PM
 * 题目建议java用character处理，而且要in place，就是不要用超过1个charArray,只在array内改动。 <--主要的难点
 * 这时只能根据替换前后两个不同的CharArray的位置差，在一个CharArray中实现替换。--->通常要从后往前替换。
 *
 * 题目中表示String最后会有足够的空格空间用于替换，所以我们不必先计算这个String空间是不是够被替换。
 * 但是我们需要计算，空间是不是太多了？替换完了以后，是不是还要剩下空格。-->出于这个考虑，我计算了newLength,并最后用了trim
 *
 */
public class ReplaceSpace {
    public String replaceSpace(String s) {
    	int len = s.length();
    	if (len <1) return s;
    	char[] chArray = s.toCharArray();
    	//trueLength: from 0 to the last not-null character in the original string
    	//newLength: =trueLength+spaceCount*2, the length after replacement
    	//spaceCount: Amount of spaces in the String (Spaces at the end of the string is excluded)
    	while (len-1>=0 && chArray[len-1]==' ') len--;
    	int trueLength = len;
    	int spaceCount = 0;

    	for (int i=0; i<trueLength; i++)
    		if (chArray[i]==' ') spaceCount++;

    	int newLength = trueLength +spaceCount *2;
    	//利用位置差，从后往前替换。
    	for (int  i=trueLength-1, j=newLength-1; i>=0; i--,j--) {
    		if (chArray[i]==' ') {
    		 chArray[j--] = '0';
    		 chArray[j--] ='2';
    		 chArray[j] = '%';
    		}
    		else chArray[j]  = chArray[i];
    	}
    	s = String.valueOf(chArray);
    	return s.trim();
    }


	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ReplaceSpace rs = new ReplaceSpace();
		String s ="    d                ";
		System.out.println(rs.replaceSpace(s));

	}

}