置換文字列のスペース(C++/Java実装)

1746 ワード

問題の説明:1つの関数を実装して文字列の各スペースを「20%」に置き換えます.例:
入力:「we are happy」
出力:「we%20 are%20 happy」
問題解決の考え方:(C++実現方法)前から後ろに遍歴し、スペースに遭遇して文字を後ろに移動すると、O(n)個のスペースがある時間効率がO(n^2)であると仮定します.したがって、最適化された解法は、一度に所定の位置に移動し、まず文字列を巡回することで、文字列の長さと文字列内のスペースの数を同時に得ることができ、その後、1つのスペースに対して「%20」という3つの文字で置き換えられるので、最終文字列にあるべき長さ、2つのポインタ、1つは最終文字列の末尾、1つは元の文字列の末尾を指すことができます.順番にコピーすると、スペースが置換され、2つのポインタが重なる(つまり同じ位置を指す)と、スペースの置換が完了します.このように時間効率はO(n)である.
void replaceBlank(char string[], int length) {//length         
	if (string == NULL || length <= 0)
		return;

	int originalLength = 0;//       
	int numberOfBlank = 0; //    
	int i = 0;
	while (string[i] != '\0') {
		originalLength++;
		if (string[i] == ' ')
			numberOfBlank++;
		i++;
	}

	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--;
	}
}

(Java実装方法)
//     :  Java API  replaceAll        
public static String replaceSpace(String str) {
	String regex = " ";
	return str.replaceAll(regex, "%20");
}

//     :     ,       
public static String replaceSpace1(String str){
	StringBuilder sb = new StringBuilder(str);
	for(int i=0; i<sb.length(); i++){
		if(sb.charAt(i) == ' ')
			sb.replace(i, i+1, "%20");
	}
	return sb.toString();	
}