2 替环空格

题目描述

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

思路：

从前往后替换，后面的字符要不断往后移动，要多次移动，所以效率低下,时间复杂度 O(N2)。

从后往前，先计算需要多少空间，然后从后往前移动，则每个字符只为移动一次，这样效率更高一点。时间复杂度O(N)。

 1 public class Solution {
 2     public String replaceSpace(StringBuffer str) {
 3         int spacenum = 0;
 4         for(int i = 0;i<str.length();i++){
 5             if(str.charAt(i)==' ')
 6                 spacenum++;
 7         }
 8         
 9            int newlength = str.length() + spacenum *2;
10         int p1 = str.length()-1;
11         int p2 = newlength -1;
12         str.setLength(newlength);
13         for(;p1>=0 && p2>p1;p1--){
14             if(str.charAt(p1)==' '){
15                 str.setCharAt(p2--,'0');
16                 str.setCharAt(p2--,'2');
17                 str.setCharAt(p2--,'%');
18             }else
19                 str.setCharAt(p2--,str.charAt(p1));
20         }
21         return str.toString();
22     }
23 }

public class Solution {
    public String replaceSpace(StringBuffer str) {
        int spacenum=0;
        for(int i =0;i<str.length();i++)
            if(str.charAt(i)==' ')
                spacenum++;
        
        int newlength = str.length()+spacenum*2;
        int p1 = str.length() -1;
        int p2 = newlength-1;
        str.setLength(newlength);
        while(true){
            if(p1<0 || p2<p1) break;
            else if(str.charAt(p1)==' '){
                str.setCharAt(p2--,'0');
                str.setCharAt(p2--,'2');
                str.setCharAt(p2--,'%');
                p1--;
            }
            else
                str.setCharAt(p2--,str.charAt(p1--));
        }
            
        return str.toString();
    }
}

更新20180303

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3     # s 源字符串
 4     def replaceSpace(self, s):
 5         # write code here
 6         s = list(s)
 7         cnt = 0
 8         for i in s:
 9             if i==' ':
10                 cnt+=1
11         i = len(s)-1
12         s = s + [' ']*cnt*2
13         j = len(s)-1
14         while i>=0 and j>=0:
15             if(s[i]!=' '):
16                 s[j] = s[i]
17                 i-=1;j-=1
18             else:
19                 s[j] = '0'
20                 s[j-1] = '2'
21                 s[j-2] = '%'
22                 j-=3
23                 i-=1
24         return ''.join(s)
25                 
26             
27

trcik

1 # -*- coding:utf-8 -*-
2 class Solution:
3     # s 源字符串
4     def replaceSpace(self, s):
5         # write code here
6         return s.replace(' ','%20')
7                 
8             
9