创意标题匹配问题

问题描述

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

解题思路

首先使用正则表达式将模板中的通配符替换为 .*，用来匹配任意字符。

遍历标题列表，对每个标题使用正则表达式进行匹配。

如果匹配成功，并且匹配的结束位置是标题的末尾，则说明该标题是由模板替换生成的，将结果设为 True，否则设为 False。

将所有结果拼接成一个字符串，以逗号分隔，作为最终输出。

代码实现

Cangjie

import std.regex.*

func solution(n: Int64, template: String, titles: Array<String>){
    let pattern = Regex("{.*?}").matcher(template).replaceAll(".*")
    let results = Array<String>(n, repeat: "False")
    for (i in 0..n) {
        let matchData = Regex(pattern).matches(titles[i])
        ifSome(matchData){ _ => results[i] = "True" }
    }
    String.join(results, delimiter: ",")
}

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

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

Rust

 extern crate regex;
 use regex::Regex;

fn solution(_n: usize, template_: &str, titles: Vec<&str>) -> String {
    let regex_template = Regex::new(r"\{.*?\}").unwrap()
        .replace_all(template_, ".*?") + "$";
    let re = Regex::new(&regex_template).unwrap();
    let mut results = Vec::new();
    for title in titles {
        let match_result = re.is_match(title);
        if match_result { results.push("True") }
        else { results.push("False") }
    }
    results.join(",")
}

 fn main() {
   let test_titles1 = vec![
        "adcdcefdfeffe", "adcdcefdfeff", 
        "dcdcefdfeffe", "adcdcfe"
    ];
    let test_titles2 = vec![
        "CLSomGhcQNvFuzENTAMLCqxBdj", "CLSomNvFuXTASzENTAMLCqxBdj",
        "CLSomFuXTASzExBdj", "CLSoQNvFuMLCqxBdj",
        "SovFuXTASzENTAMLCq", "mGhcQNvFuXTASzENTAMLCqx",
    ];
    let test_titles3 = vec!["abcdefg", "abefg", "efg"];

    println!("{}", solution(4, "ad{xyz}cdc{y}f{x}e", test_titles1) ==
        "True,False,False,True");
    println!("{}", solution(6, "{xxx}h{cQ}N{vF}u{XTA}S{NTA}MLCq{yyy}", 
        test_titles2) == "False,False,False,False,False,True"
    );
    println!("{}", solution(3, "a{bdc}efg", test_titles3) ==
        "True,True,False");
 }

python

import re
def solution(n, template_, titles):
    pattern = re.sub(r'\{.*?\}', '.*?', template_)
    regex = re.compile(pattern)
    results = []
    for title in titles:
        if regex.fullmatch(title):
            results.append("True")
        else:
            results.append("False")
    return ",".join(results)

testTitles1 = ["adcdcefdfeffe", "adcdcefdfeff", "dcdcefdfeffe", "adcdcfe"]
testTitles2 = [
    "CLSomGhcQNvFuzENTAMLCqxBdj", "CLSomNvFuXTASzENTAMLCqxBdj", 
    "CLSomFuXTASzExBdj", "CLSoQNvFuMLCqxBdj", 
    "SovFuXTASzENTAMLCq", "mGhcQNvFuXTASzENTAMLCqx"
]
testTitles3 = ["abcdefg", "abefg", "efg"]

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

JavaScript

function solution(n, template_, titles) {
    let pattern = template_.replace(/{.*?}/g, '.*?');
    let regex = new RegExp(`^${pattern}$`);
    let results = [];
    for (let title of titles) {
        if (regex.test(title)) {
            results.push("True");
        } else {
            results.push("False");
        }
    }
    return results.join(",");
}

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");

复杂度分析

时间复杂度：O(n)，其中 n 是标题的数量。对于每个标题，我们需要进行一次正则表达式匹配，时间复杂度为 O(m)，其中 m 是标题的长度。因此总时间复杂度为 O(nm)。

空间复杂度：O(n)，其中 n 是标题的数量。我们需要一个列表来存储每个标题的匹配结果，列表的大小为 n。

仓颉编程语言