《剑指Offer》面试题四之替换空格

2019-11-06 07:25:22

字体：大中小

来源：转载

供稿：网友

题目描述

请实现一个函数，将一个字符串中的空格替换成“%20”。例如：当字符串为We Are Happy. 则经过替换之后的字符串为We%20Are%20Happy。

题目分析

直观的做法就会从头到尾扫描字符串，遇到空格时就做替换。由于是把一个字符替换成了三个字符，所以后面的字符串得整体往后挪动两位。这时候我们会发现，如果空格的数目过多，就会让问题过于复杂化，时间复杂度也会达到O(n^2)。但是如果先的得到该字符串(长度假设为n)中空格的数目，假设为m，那么替换后的字符串的长度应该为 n+2*m，这时候申请这样长度的一个数组，从后向前一个字符一个字符的复制，这样时间复杂度就是O(n)。相信你看到下面的代码就会明白我的意思。

算法设计

public static String getTempString(String str,int spaceNum){//传入字符串，以及字符串中空格的数目 char[] tempStr=new char[str.length()+2*spaceNum]; //初始化一个长度为替换后的字符串的长度的数组 int j=tempStr.length-1; for(int i=str.length()-1;i>=0;i--){ if(str.charAt(i)==' '){ //如果是空格，将当前位置以及前面的两个位置替换为 % 2 0 tempStr[j--]='0'; tempStr[j--]='2'; tempStr[j--]='%'; }else{ //反之，直接复制 tempStr[j--]=str.charAt(i); } } return new String(tempStr); }