7. 创意标题匹配问题

刷题前请喊一遍我们的口号：

• 方法不对，刷题白费。
• 节省时间，精准刷题。

本题难度系数：⭐简单

问题描述

在广告平台中，为了给广告主一定的自由性和效率，允许广告主在创造标题的时候以通配符的方式进行创意提交。线上服务的时候，会根据用户的搜索词触发的 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"

解题思路

这个问题需要判断给定的标题是否可以从模板通过替换通配符生成。关键在于如何将模板转换为一个可以匹配的模式，然后检查每个标题是否符合这个模式。

1. 解析模板：将模板拆分为固定部分和通配符部分。例如，模板 "ad{xyz}cdc{y}f{x}e" 可以拆分为固定部分 ["ad", "cdc", "f", "e"] 和通配符部分 ["xyz", "y", "x"]。
2. 构建正则表达式：将固定部分和通配符部分转换为正则表达式。固定部分需要原样匹配，通配符部分可以匹配任意字符（包括空字符串）。例如，模板 "ad{xyz}cdc{y}f{x}e" 对应的正则表达式可以是 /^ad.*cdc.*f.*e$/。
3. 匹配标题：对于每个标题，使用构建的正则表达式进行匹配，判断是否符合模式。

开始解题

function solution(n, template_, titles) {
  // 将模板转换为正则表达式
  const regexStr = template_.replace(/\{[^}]*\}/g, '.*');
  const regex = new RegExp(`^${regexStr}$`);
  
  // 检查每个标题是否匹配正则表达式
  const results = titles.map(title => regex.test(title) ? "True" : "False");
  
  // 返回结果字符串
  return results.join(",");
}

function main() {
  const testTitles1 = ["adcdcefdfeffe", "adcdcefdfeff", "dcdcefdfeffe", "adcdcfe"];
  const testTitles2 = ["CLSomGhcQNvFuzENTAMLCqxBdj", "CLSomNvFuXTASzENTAMLCqxBdj", "CLSomFuXTASzExBdj", "CLSoQNvFuMLCqxBdj", "SovFuXTASzENTAMLCq", "mGhcQNvFuXTASzENTAMLCqx"];
  const testTitles3 = ["abcdefg", "abefg", "efg"];

  console.log(solution(4, "ad{xyz}cdc{y}f{x}e", testTitles1) === "True,False,False,True");
  console.log(solution(6, "{xxx}h{cQ}N{vF}u{XTA}S{NTA}MLCq{yyy}", testTitles2) === "False,False,False,False,False,True");
  console.log(solution(3, "a{bdc}efg", testTitles3) === "True,True,False");
}

main();

代码解释

1. 正则表达式转换：使用 replace 方法将所有通配符（{...}）替换为 .*，这样可以匹配任意字符（包括空字符串）。
2. 构建正则表达式：使用 new RegExp 构建正则表达式，并添加 ^ 和 $ 确保从头到尾完全匹配。
3. 匹配标题：对每个标题使用 test 方法检查是否匹配正则表达式，返回 "True" 或 "False"。
4. 结果拼接：将结果数组拼接为字符串返回。

这种方法的时间复杂度为 O(n * m)，其中 n 是标题数量，m 是标题的平均长度，空间复杂度为 O(1)（不考虑正则表达式的存储）。这是最优的解法，因为必须检查每个标题的每个字符。

以上关于7. 创意标题匹配问题的文章就介绍到这了，更多相关内容请搜索码云笔记以前的文章或继续浏览下面的相关文章，希望大家以后多多支持码云笔记。