掘金--创意标题匹配问题

问题描述

在广告平台中，为了给广告主一定的自由性和效率，允许广告主在创造标题的时候以通配符的方式进行创意提交。线上服务的时候，会根据用户的搜索词触发的 bidword 对创意中的通配符（通配符是用成对 {} 括起来的字符串，可以包含 0 个或者多个字符）进行替换，用来提升广告投放体验。例如：“{末日血战} 上线送 SSR 英雄，三天集齐无敌阵容！”，会被替换成“帝国时代游戏下载上线送 SSR 英雄，三天集齐无敌阵容！”。给定一个含有通配符的创意和n个标题，判断这句标题是否从该创意替换生成的。

测试样例

样例1：

输入：n = 4, template = “ad{xyz}cdc{y}f{x}e”, titles = [“adcdcefdfeffe”, “adcdcefdfeff”, “dcdcefdfeffe”, “adcdcfe”]
输出：“True,False,False,True”

样例2：

输入：n = 3, template = “a{bdc}efg”, titles = [“abcdefg”, “abefg”, “efg”]
输出：“True,True,False”

样例3：

输入：n = 5, template = “{abc}xyz{def}”, titles = [“xyzdef”, “abcdef”, “abxyzdef”, “xyz”, “abxyz”]
输出：“True,False,True,True,True”

思路分析

看到这个题的第一想法就是？？？
题目并没有说明数据范围，如果数据范围过大不上点手段的话，肯定无法a掉的：）
但是这道题只是简单难度，所以猜它的数据规模并不大，暴力大概率能过。但是写暴力感觉很无聊，脑袋中突然想到我们在实际开发过程中也会遇到这种匹配的问题，比如邮箱格式验证等。
所以我们这里可以使用正则表达式来解决，由于正则学的不咋样，这里求救了一下伟大的GPT之神，顺利a掉。
时间复杂度:$O(n\cdot (k\cdot m+p+q))$
其中：
$n$：标题数量；
$k$：模板中的 {} 数量；
$m$：模板长度；
$p$：正则表达式长度；
$q$：标题长度。

#include <iostream>
#include <string>
#include <vector>
#include <regex>
using namespace std;bool isGeneratedTitle(const string& templateStr, const string& title) {// 将模板中的通配符 {} 替换为正则表达式 (.*)string pattern = templateStr;size_t pos = 0;// 替换所有的 {} 为 (.*)while ((pos = pattern.find("{", pos)) != string::npos) {size_t end = pattern.find("}", pos);if (end == string::npos) break; pattern.replace(pos, end - pos + 1, "(.*?)");pos += 4; }// 在正则表达式中添加开始和结束标记pattern = "^" + pattern + "$";// 使用正则表达式匹配regex re(pattern);return regex_match(title, re);
}std::string solution(int n, std::string template_,std::vector<std::string> titles) {// Please write your code herestring ans = "";for(int i = 0; i < n; ++i){if(ans.size() != 0){ans += ",";}if (isGeneratedTitle(template_, titles[i])){ans += "True";} else {ans += "False";}}return ans;
}