题目描述

查找和替换一段字符串input,找出字符串中包含在方括号(“[“、 “]”) 之间(即起始于“[”而结束于””)的内容，如果完全匹配特定的内容searchFor,则将其(包括起止方括号字符)替换为另一特定的内容replaceWith。

如: input为”abc[d]efdg” , searchFor为”d”, replaceWith为”x”, 则处理后的结果为”abcxefdg”。

算法1

(暴力枚举)

C++ 代码

class Solution {
public:
    /*
    每次查找到[以后就看[后面的searchFor.size个字符是不是和searchFor相等,相等就替换。
    */
    string SearchAndReplace(string input, string searchFor, string replaceWith) {
        // write code here
        string output;
        int l = searchFor.size();
        for (int i = 0; i < input.size(); ++i)
        {
            if ('[' == input[i] && i + l + 1 < input.size() && ']' == input[i + l + 1] && input.substr(i + 1, l) == searchFor)
            {
                output += replaceWith;
                i = i + l + 1;
            }
            else output.push_back(input[i]);
        }

        return output;
    }
};

算法2

(字符串哈希)

typedef unsigned long long ull;
const int P = 131;
const int N = 1e5 + 10;
ull h[N],p[N];
class Solution3 {
public:
    /*
    字符串哈希
    */
    ull find(int l, int r)
    {
        return h[r] - h[l - 1] * p[r - l + 1];
    }

    string SearchAndReplace(string input, string searchFor, string replaceWith) {
        // write code here
        if (input.size() < searchFor.size())    return input;
        string output;
        searchFor.insert(0, "[");
        searchFor.push_back(']');
        int l = searchFor.size();
        p[0] = 1;
        for (int i = 1; i <= input.size(); ++i)
        {
            h[i] = h[i - 1] * P + input[i - 1];
            p[i] = p[i - 1] * P;
        }
        ull st;
        for (int i = 1; i <= l; ++i)
        {
            st = st * P + searchFor[i - 1];
        }
        for (int i = 0; i < input.size(); ++i)
        {
            if (i + l - 1 < input.size() && find(i + 1, i + l) == st)
            {
                output += replaceWith;
                i = i + l - 1;
            }
            else
                output.push_back(input[i]);
        }
        return output;
    }
};