字符串空格替换

题目描述

请实现一个函数，将一个字符串中的空格替换成”20%”,例如，当字符串为we are happy，则经过替换之后的字符串为we%20are%20happy；

思路分析

这个首先让人想到的是java中不是有replaceAll（）方法（源码模拟在之前的数据结构中已总结），如果直接调用那就没意思了，或者使用stringBuffer的append（）方法，遇到空格在后面插入，这样做也可以，但是是不是也是体现不出我们的思考过程。另一种做法就是

大概意思就是构造一个缓存数组temp，首先计算出原字符数组中的空格数，而temp的大小就是原数组长度加上空格数*2，同时先将原数组拷贝到新数组，多出的空间刚开始是空值，然后有两个索引，分别指向原数组末尾和新数组末尾，最后通过原数组末尾一个一个字符的从后向前比较，如果是空值的话，替换，否则将原数组的内容在新数组中向后移动至末尾，依次，知道原数组索引小于0为止，代码如下

public class Buffer {

	public String replaceSpace(StringBuffer s){
		String str=s.toString();
		 int blankCount=this.getBlankCount(str);
		  int originLen=str.toCharArray().length;
		    int newStrlen=blankCount*2+originLen;
		     char[] newStr=new char[newStrlen];
		      System.arraycopy(str.toCharArray(), 0, newStr, 0, originLen);
		      int strIndex=originLen-1;
		       int newstrIndex=newStrlen-1;
		        while(strIndex>0&&strIndex!=newstrIndex)
		        {
		        	if(str.charAt(strIndex)==' '){
		        		newStr[newstrIndex--]='0';
		        		newStr[newstrIndex--]='2';
		        		newStr[newstrIndex--]='%';
		        	}
		        	else{
		        		newStr[newstrIndex--]=newStr[strIndex];
		        	}
		        	strIndex--;
		        }
		        return new String(newStr);
	}
	

	public int getBlankCount(String s){
		int count=0;
		 for(int i=0;i<s.length();i++){
			 if(s.charAt(i)==' ')
				 count++;
		 }
		 return count;
	}
	
}

测试类：

String s=”we are happy”;
StringBuffer sb=new StringBuffer(s);
String str=new Buffer().replaceSpace(sb);
System.out.println(str);

可以发现整个过程都是一层循环，所以它的时间复杂度为O(n);

其他解法

replaceAll方法

String str=s.replaceAll("\\s", "20%");
	System.out.println(str);

其中此方法需要传正则表达式，而\s表示空格，当然结果也能完成目的，但是考虑到String是不变字符串，也就是说它不能在原来字符数组上进行修改，需要另开内存空间，所以每次插入，都要向后移动n此，同时也要查找比较n词，显然时间复杂度就是O（n*2），来看看之前模拟的replaceAll方法

public MyString replaceAll(MyString pattern,MyString replacement){
		MyString temp=new MyString(this);
		 int i=this.indexOf(pattern, 0);
		  while(1!=-1)
		  {
			  temp=temp.substring(0, i).concat(replacement).concat(this.substring(i+pattern.length()));
			  i=temp.indexOf(pattern, i+replacement.length());//从下一个字符开始继续寻找匹配
		  }
	}

显然此方法效率不高

stringBuffer方法

public String replace(String input){
		if(input==null){
			return null;
		}
		StringBuffer str=new StringBuffer();
		 for(int i=0;i<input.length();i++){
			 if(input.charAt(i)==' ')
			 {
				 str.append("%");
				 str.append("2");
				 str.append("0");
			 }
			 else{
				 str.append(String.valueOf(input.charAt(i)));
			 }
		 }
		
		 return new String(str);
		
	}

主要利用stringBuffer的可变性，同样只有一层循环，时间复杂度为O（n）；