题目描述
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
1 package Solution; 2 3 /** 4 * 剑指offer面试题4：替换空格 5 * 题目：请事先一个函数，把字符串中的每个空格替换成"%20"。 6 * 例如输入"We are happy."，则输出"We%20are%20happy."。 7 * @author GL 8 * 9 */ 10 public class No4ReplaceSpace { 11 12 public static void main(String[] args) { 13 String string1="We are happy."; 14 String string2=" We are happy. "; 15 String string3="Wearehappy."; 16 //String string4=null; 17 String string5=""; 18 String string6=" "; 19 String string7=" "; 20 System.out.println(replaceSpace(string1.toCharArray())); 21 System.out.println(replaceSpace(string2.toCharArray())); 22 System.out.println(replaceSpace(string3.toCharArray())); 23 //System.out.println(replace(string4.toCharArray())); 24 System.out.println(replaceSpace(string5.toCharArray())); 25 System.out.println(replaceSpace(string6.toCharArray())); 26 System.out.println(replaceSpace(string7.toCharArray())); 27 System.out.println(replaceSpace(new StringBuffer(string1))); 28 System.out.println(replaceSpace(new StringBuffer(string2))); 29 System.out.println(replaceSpace(new StringBuffer(string3))); 30 //System.out.println(replaceSpace(new StringBuffer(string4))); 31 System.out.println(replaceSpace(new StringBuffer(string5))); 32 System.out.println(replaceSpace(new StringBuffer(string6))); 33 System.out.println(replaceSpace(new StringBuffer(string7))); 34 } 35 36 /* 37 * 时间复杂度为O(n)的解法：利用数组从后向前替换 38 * 1、先遍历一次字符串，统计出要替换的字符的个数 39 * 2、创建新的临时数组，数组长度为初始字符串字符个数+替换每个字符多出来的字符个数*要替换的字符个数 40 * 3、从原来字符串数组后面开始向前进行复制、替换到临时数组。两个数组下标变量分别为原始字符数组长度-1，临时数组长度-1 41 * 4、原始字符数组的字符如果不为空格，则把这个字符复制到临时数组的对应位置，两个数组下标都减1 42 * 5、原始字符数组的字符如果为空格，则把临时数组相对应的位置从后向前依次写入替换的字符，临时数组下标减少相应的替换的字符数量 43 * 6、循环复制替换，直到初始数组的下标小于0，此时替换完毕，临时数组转换成字符串后返回 44 */ 45 public static String replaceSpace(char[] string){ 46 if(string==null) 47 return null; 48 int originalLength=string.length; 49 int spaceCount=0; 50 for(int i=0;i<originalLength;i++){ 51 if(string[i]==' ') 52 spaceCount++; 53 } 54 int newLength=originalLength+2*spaceCount; 55 char[] temp=new char[newLength]; 56 int i=originalLength-1; 57 int j=newLength-1; 58 while(i>=0){ 59 if(string[i]==' '){ 60 temp[j]='0'; 61 temp[j-1]='2'; 62 temp[j-2]='%'; 63 j=j-3; 64 }else{ 65 temp[j]=string[i]; 66 j=j-1; 67 } 68 i=i-1; 69 } 70 return new String(temp); 71 } 72 73 /* 74 * 时间复杂度为O(n)，利用StringBuffer实现 75 * 通过indexOf(String str,int fromIndex)方法和subSequence(int start,int end)方法联合实现 76 */ 77 public static String replaceSpace(StringBuffer str){ 78 if(str==null) 79 return null; 80 int fromIndex=0; 81 int index=0; 82 StringBuffer temp =new StringBuffer(); 83 while(index<=str.length()){ 84 index=str.indexOf(" ",fromIndex); 85 if(index>=0){ 86 temp.append(str.subSequence(fromIndex, index)).append("%20"); 87 index=index+1; 88 fromIndex=index; 89 }else{ 90 temp.append(str.substring(fromIndex, str.length())); 91 break; 92 } 93 } 94 return temp.toString(); 95 } 96 97 }