leetcode 剑指 Offer 05 替换空格

谁借莪１个温暖的怀抱￠ 2022-09-10 04:22 138阅读 0赞

## 前言 ##

题目：[剑指 Offer 05. 替换空格][Offer 05.]

参考答案：[替换空格-力扣官方题解][-]

--------------------

## 提交代码 ##

**字符串中的替换有四种：字符-替换成字符，字符-替换成字符串，字符串-替换成字符，字符串-替换成字符串**。

字符-替换成字符，这种情况，存储空间不用改变，很容易处理。

这道题目是，字符-替换成字符串，需要改变空间。这里提供两种做法。第一种使用附加空间，边读取边处理。第二种是扩展原来的空间。我推荐使用第一种做法。

而，关于字符串-替换成字符，字符串-替换成字符串，不仅需要改变空间，还设计字符串匹配查找问题。我暂时没想好思路。

### 使用附加空间 ###

class Solution {
    public:
        string replaceSpace(string s) {
            string result;
            istringstream ss(s);
            char needReplaceAlpha = ' ';
            string substitution = "%20";
    
            char ch;
            while(ss>>noskipws>>ch){
                if(ch != needReplaceAlpha)
                    result+=ch;
                else
                    result+=substitution;
            }
    
            return result;
        }
    };

### 扩展原来空间 ###

class Solution {
    public:
        string replaceSpace(string s) {
            char needReplaceAlpha = ' ';
            string substitution = "%20";
    
            int oldSize = s.size();
    
            // 统计需要替换的字符串个数
            int count=0;
            for(auto ch : s){
                if(ch == needReplaceAlpha)
                    count++;
            }        
    
            // 调整字符串的大小
            s.resize(s.size()+count*substitution.size()-count);
            int newSize = s.size();
    
            // 进行替换操作
            int i = oldSize-1; 
            int j = newSize-1;
            while(i >= 0){
                if(s[i] != needReplaceAlpha){
                    s[j] = s[i];
                    j--;
                    i--;
                }else{
                    for(auto it = substitution.rbegin(); it!=substitution.rend(); it++)
                        s[j--] = *it;
                    i--;
                }
            }
    
            return s;
        }
    };

[Offer 05.]: https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/
[-]: https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/solution/mian-shi-ti-05-ti-huan-kong-ge-by-leetcode-solutio/