字节跳动 算法实习生-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;
};
