3606. 优惠码验证器

Source: Dev.to

问题描述

给定三个长度为 n 的数组，描述 n 张优惠券的属性：

• code[i]：表示优惠券标识的字符串。
• businessLine[i]：表示优惠券业务类别的字符串。
• isActive[i]：布尔值，指示优惠券当前是否处于激活状态。

当且仅当满足以下所有条件时，优惠券被视为 有效：

1. code[i] 非空且仅由字母、数字 (a‑z, A‑Z, 0‑9) 和下划线 (_) 组成。
2. businessLine[i] 必须是以下四类之一："electronics"、"grocery"、"pharmacy"、"restaurant"。
3. isActive[i] 为 true。

返回所有有效优惠券的代码数组，首先按 businessLine 的顺序

"electronics" → "grocery" → "pharmacy" → "restaurant"

排序，在每个类别内部再按 code 的字典序（升序）排序。

示例 1

输入

code = ["SAVE20", "", "PHARMA5", "SAVE@20"]
businessLine = ["restaurant", "grocery", "pharmacy", "restaurant"]
isActive = [true, true, true, true]

输出

["PHARMA5", "SAVE20"]

解释

• 第一个优惠券有效。
• 第二个优惠券代码为空 → 无效。
• 第三个优惠券有效。
• 第四个优惠券包含特殊字符 @ → 无效。

过滤后，剩余的代码按业务线（pharmacy 在 restaurant 前）以及代码本身排序。

示例 2

输入

code = ["GROCERY15", "ELECTRONICS_50", "DISCOUNT10"]
businessLine = ["grocery", "electronics", "invalid"]
isActive = [false, true, true]

输出

["ELECTRONICS_50"]

解释

• 第一个优惠券未激活 → 无效。
• 第二个优惠券有效。
• 第三个优惠券业务线不在允许范围内 → 无效。

约束条件

• n == code.length == businessLine.length == isActive.length
• 1 ≤ n ≤ 100
• 0 ≤ code[i].length, businessLine[i].length ≤ 100
• code[i] 和 businessLine[i] 由可打印的 ASCII 字符组成。
• isActive[i] 只能是 true 或 false。

提示

1. 过滤掉任何满足以下任意条件的优惠券：
   • isActive[i] 为 false；
   • code[i] 为空或包含非字母数字/下划线的字符；
   • businessLine[i] 不在允许集合中。
2. 将每个剩余的优惠券存为 (businessLine[i], code[i]) 对。
3. 定义一个优先级映射，例如 { "electronics":0, "grocery":1, "pharmacy":2, "restaurant":3 }。
4. 按 (priority[businessLine], code) 对对列表进行排序，并按顺序返回代码值。

解题思路概述

1. 校验

   • 使用正则表达式 ^[a-zA-Z0-9_]+$ 检查 code。
   • 确认 isActive 为 true。
   • 确保 businessLine 属于允许集合。

2. 映射优先级
   创建一个关联数组，将每个业务线映射到其排序优先级。

3. 排序

   • 将所有有效优惠券收集为形如 { "line": ..., "code": ... } 的数组。
   • 使用 usort 并自定义比较函数，先比较优先级值，再按代码的字典序（strcmp）比较。

4. 结果提取
   排序完成后，仅提取 code 字段组成最终结果数组。

PHP 实现

 0,
        "grocery"     => 1,
        "pharmacy"   => 2,
        "restaurant" => 3,
    ];

    $valid = [];

    $n = count($code);
    for ($i = 0; $i  $businessLine[$i],
            'code' => $code[$i],
        ];
    }

    // Sort by business line priority, then by code lexicographically
    usort($valid, function ($a, $b) use ($priority) {
        $pA = $priority[$a['line']];
        $pB = $priority[$b['line']];

        if ($pA !== $pB) {
            return $pA  $pB;
        }
        return strcmp($a['code'], $b['code']);
    });

    // Extract only the codes
    return array_column($valid, 'code');
}

// ----- Test cases -----
print_r(validateCoupons(
    ["SAVE20", "", "PHARMA5", "SAVE@20"],
    ["restaurant", "grocery", "pharmacy", "restaurant"],
    [true, true, true, true]
)); // Expected: ["PHARMA5", "SAVE20"]

print_r(validateCoupons(
    ["GROCERY15", "ELECTRONICS_50", "DISCOUNT10"],
    ["grocery", "electronics", "invalid"],
    [false, true, true]
)); // Expected: ["ELECTRONICS_50"]
?>

复杂度分析

• 时间复杂度： O(n log n) — 过滤为线性时间，排序是主导，n 为有效优惠券的数量（≤ 100）。
• 空间复杂度： O(n) — 用于存放有效优惠券的额外数组。