【第三轮】6.16-6.22 CareerCup 1.4

1.4 Write a method to replace all spaces in a string with'%20'. You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the "true" length of the string. (Note: if implementing in Java, please use a character array so that you can perform this operation in place.)   
EXAMPLE
Input: "Mr John Smith       "
Output: "Mr%20Dohn%20Smith"  
         
回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
遍历 char 数组计算新数组的长度；
从后往前copy，并将空格改为 %20
【时间复杂度】
  O(n)
【空间复杂度】
  O(1)
【gist link】
https://gist.github.com/JoyceeLee/60a6d8d88866845f4461

【解题思路】
since the string in c++ STL is mutable, it is very easy to solve this problem.
If we can not use string. First count the number of space in the string, then we assign a new string size of (size(oldstring)+count(space)), and we scan from the end of string, when we meet a space, we replace it by "%20".
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/qianhuang/8d23c5c0309ea246d470

donnice 发表于 2014-6-29 05:35
【解题思路】
把所有的string转化为char，碰到空格就转化为'%20'（感谢沙发给予的启发）
【时间复杂度】
...

public class Stringtest{
        public static void main(String[] args){
                String t = "da ben dan sha bi a";
                int p = 0;
                for(int n = 0; n<t.length();n++){
                        if(t.charAt(n) == ' ')
                                p++;
                }
                int k = t.length()+2*p+1;
                char[] result = new char[k];
                int j = 0;
                for(int i = 0; i<t.length();i++){
                        if(t.charAt(i)!=' '){
                                result[j] = t.charAt(i);
                                j++;
                        }
                        else{
                                result[j] = '%';
                                result[j+1] = '2';
                                result[j+2] = '0';
                                j =j+3;
                        }
                }
                for(int m = 0; m<=j; m++)
                        System.out.print(result[m]);
        }
}
楼上有些错误，不好意思……

【解题思路】
先计算需要空间 用char[] 存放 然后转回 String
【时间复杂度】
N
【空间复杂度】
N
【gist link】
https://gist.github.com/atlas1017/d45f5885a83bbfefb800
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】
go through all elems in String, replace space with %20

first time write this in rec
【时间复杂度】
n
【空间复杂度】
n
【gist link】
https://gist.github.com/gaoyike/9a7198ada98a932e37b7

【解题思路】
  Split the whole string by space, save each word in an array.
  Concatenate and put "%20" in between each word
【时间复杂度】
  O(N)
【空间复杂度】
  O(1)
【gist link】
https://gist.github.com/habina/cb4d5c96bc98ac87b26c

【解题思路】
first find the index where the actual string ends
then calculate the number of spaces to be converted to assure the length of the result string
use two pointers, one pointing to the end of the former string, the other pointing to the end of the result string
then move pointers backwards to convert spaces one by one, and this can be done in-place.
【时间复杂度】
  O(n)
【空间复杂度】
  O(1)
【gist link】
  https://gist.github.com/monkerek/61cbc179c97c5d263beb

【解题思路】first find the "true length" of the string, then whenever we find a space, we count how many spots for this space and then shift the char[] left/right by corresponding amount of spots and then replace space by %20 (感觉自己写的code很复杂, 求各位大神指点, 小弟第一次刷...)
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/startupjing/65f591967d74c78bc2d4
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】case when multiple spots in a space, like "Mr    John  Smith           "

【解题思路】Traverse the array. Move every character into the result array by order. Insert "%20" when encounter a " ".
【时间复杂度】O(n) for traversing array once.
【空间复杂度】O(n) for tripling the size of the original array.
【gist link】https://gist.github.com/a833f1d440a33843c0ad.git

求好的test case

readman 发表于 2014-6-16 12:06
【解题思路】
go through all elems in String, replace space with %20

为什么会想到用recursion来做这道题！