面试金典0103 URL化

题目：URL化

解题方法：

新建字符串，双指针法
在S上从后往前，双指针法

两种解法时间复杂度一样，都是\(O(n)\)，解法二不需要额外的空间

解法一：

这里可以通过初始化一个和S相同大小的string来存储新的序列，这里直接用[p2]来寻址就可以了，最后用erase(int pos, int len)来删除从pos开始长度为len的字符串
也可以新建一个空的字符串，用insert(int pos, string s)来在pos处插入string字符串，或用push_back(char c)来在string末尾添加char字符

class Solution {
public:
    string replaceSpaces(string S, int length) {
        string S2 = S; // 不初始化就不能用S2[p2]这样的寻址方法，而应该用push_back(char c)
        int p2 = 0;
        for(int p1=0; p1<length; ++p1)
        {
            if(S[p1] != ' ')
            {
                S2[p2++] = S[p1];
            }
            else
            {
                S2[p2++] = '%';
                S2[p2++] = '2';
                S2[p2++] = '0';
            }
        }
        S2.erase(p2); // erase(int start [, int len])，从start开始，删除len个长度，没有len的话会删除start开始的所有字符
        return S2;
    }
};

class Solution {
public:
    string replaceSpaces(string S, int length) {
        string s2;
        s2 = "";
        for(int i=0, j=0; i<length; ++i)
        {
            if(S[i] == ' ')
            {
                s2.insert(j++, "%"); // 注意这里insert后面用的是string类型 或者是char *，即字符数组，而不是char '%'
                s2.push_back('2'); // 这里可以用push_back()，此时就是char类型，而不是char *
                j++;
                s2.insert(j++, "0");
            }
            else
            {
                string tmp(1, S[i]); // 将S[i]转化为字符串类型，再使用insert
                s2.insert(j++, tmp);
            }
        }
        // s2.insert(0, "abc");
        return s2;
    }
};

解法二：

因为题目中说S的长度够长，因此可以利用双指针，一个从S的末尾开始，一个从给定字符串长度开始，从后往前遍历。最后删掉S前面多余的部分即可

class Solution {
public:
    string replaceSpaces(string S, int length) {
        int j = S.size() -1;
        for(int i = length-1; i>=0; --i)
        {
            if(S[i] == ' ')
            {
                S[j--] = '0';
                S[j--] = '2';
                S[j--] = '%';
            }
            else
            {
                S[j--] = S[i];
            }
        }
        S.erase(0, j+1); // j多减了1，因此要加回来
        return S;
    }
};