字节跳动算法实习生-Data 三面【已感谢】

题目：查找长字符串A中的短字符串B并将其替换为短字符串C。要求：尽量少申请额外空间，时间复杂度低。

当场认为是KMP，直接蒙了。。。后来只写对了一半，缩减A的。扩张A的想到了，面试官没让讲，时间太长了。最后面试官说还要处理多次替换的情况。。跪了。。。

#include<iostream>
#include<string>
using namespace std;

class Solution {
public:
    //判断A从第k个元素起始是否与B相同
    bool replace_B(string A, int k, int len2, string B)
    {
        for (int i = 0; i < len2; i++)
        {
            if (A[k + i] != B[i])
            {
                return false;
            }
        }
        return true;
    }
    //判断A从第k个元素起终点是否与B相同
    bool rreplace_B(string A, int k, int len2, string B)
    {
        for (int i = 0; i <len2; i++)
        {
            if (A[k - i] != B[len2-1-i])
            {
                return false;
            }
        }
        return true;
    }

    void replace(string &A, string B, string C)
    {
        int len1 = A.size();
        int len2 = B.size();
        int len3 = C.size();
        int count = 0;
        for (int i = 0; i < len1; i++)            //遍历A字符串中B字符串的个数
        {
            count += (int)replace_B(A, i, len2, B);
        }
        if (len2 >= len3)                        //缩减A：从前往后
        {
            int j = 0;
            for (int i = 0; i < len1; i++)
            {
                
                if (replace_B(A, i, len2, B))
                {
                    for (int t = 0; t < len3; t++)
                    {
                        A[j++] = C[t];
                     }
                    i += len2 - 1;
                }
                else
                {
                    A[j++] = A[i];
                }    
            }
            int k = len2 - len3;
            A.resize(A.size() - count * k);

        }
        else                                    //扩张A：从后往前
        {
            int k = len3 - len2;
            A.resize(A.size() + count * k);
            int j = A.size()-1;
            for (int i = len1 - 1; j > i; i--)
            {
                if (rreplace_B(A, i, len2, B))
                {
                    for (int t = len3 - 1; t >= 0; t--)
                    {
                        A[j--] = C[t];
                    }
                    i -= len2 - 1;
                }
                else
                {
                    A[j--] = A[i];
                }
            }
        }
    }
};

int main() {
    Solution s;
    string A = "ABCDEFABC";
    string B = "ABC";
    string C = "A";
    s.replace(A, B, C);
    cout << A <<endl;
    return 0;
};

#实习##面经##字节跳动##算法工程师#