Easy

题目描述

给你三个长度为 n 的数组，描述 n 张优惠券的属性：code、businessLine 和 isActive。第 i 张优惠券具有：

  • code[i]：表示优惠券标识符的字符串。
  • businessLine[i]：表示优惠券业务类别的字符串。
  • isActive[i]：表示优惠券当前是否有效的布尔值。

如果满足以下所有条件，则认为优惠券是有效的：

  • code[i] 非空且仅由字母数字字符（a-z、A-Z、0-9）和下划线（_）组成。
  • businessLine[i] 是以下四个类别之一：“electronics”、“grocery”、“pharmacy”、“restaurant”。
  • isActive[i] 为 true。

返回所有有效优惠券代码的数组，首先按 businessLine 的顺序排序：“electronics”、“grocery”、“pharmacy”、“restaurant”，然后在每个类别内按代码的字典序（升序）排序。

示例 1：

输入：code = ["SAVE20","","PHARMA5","SAVE@20"], businessLine = ["restaurant","grocery","pharmacy","restaurant"], isActive = [true,true,true,true]
输出：["PHARMA5","SAVE20"]
解释：
- 第一张优惠券有效。
- 第二张优惠券代码为空（无效）。
- 第三张优惠券有效。
- 第四张优惠券包含特殊字符 @（无效）。

示例 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] 必须为 true
  • code[i] 非空且只包含字母数字和下划线
  • businessLine[i] 必须是四个指定类别之一

对于代码验证，可以遍历字符串中的每个字符，检查是否为字母、数字或下划线。

步骤2：建立排序优先级 根据题目要求，需要按特定的业务线顺序排序。可以创建一个映射表，将业务线映射到优先级数字：

  • “electronics” → 0
  • “grocery” → 1
  • “pharmacy” → 2
  • “restaurant” → 3

步骤3：排序输出 将有效的优惠券按照 (业务线优先级, 代码字典序) 的规则进行排序，最后提取代码部分作为结果。

时间复杂度主要取决于排序操作，为 O(m log m)，其中 m 是有效优惠券的数量。

代码实现

class Solution {
public:
    vector<string> validateCoupons(vector<string>& code, vector<string>& businessLine, vector<bool>& isActive) {
        unordered_map<string, int> priority = {
            {"electronics", 0}, {"grocery", 1}, {"pharmacy", 2}, {"restaurant", 3}
        };
        
        vector<pair<int, string>> validCoupons;
        
        for (int i = 0; i < code.size(); i++) {
            if (!isActive[i]) continue;
            if (code[i].empty()) continue;
            if (priority.find(businessLine[i]) == priority.end()) continue;
            
            bool validCode = true;
            for (char c : code[i]) {
                if (!isalnum(c) && c != '_') {
                    validCode = false;
                    break;
                }
            }
            
            if (validCode) {
                validCoupons.push_back({priority[businessLine[i]], code[i]});
            }
        }
        
        sort(validCoupons.begin(), validCoupons.end(), [](const auto& a, const auto& b) {
            if (a.first != b.first) return a.first < b.first;
            return a.second < b.second;
        });
        
        vector<string> result;
        for (const auto& coupon : validCoupons) {
            result.push_back(coupon.second);
        }
        
        return result;
    }
};

class Solution:
    def validateCoupons(self, code: List[str], businessLine: List[str], isActive: List[bool]) -> List[str]:
        priority = {"electronics": 0, "grocery": 1, "pharmacy": 2, "restaurant": 3}
        
        valid_coupons = []
        
        for i in range(len(code)):
            if not isActive[i]:
                continue
            if not code[i]:
                continue
            if businessLine[i] not in priority:
                continue
            
            if all(c.isalnum() or c == '_' for c in code[i]):
                valid_coupons.append((priority[businessLine[i]], code[i]))
        
        valid_coupons.sort(key=lambda x: (x[0], x[1]))
        
        return [coupon[1] for coupon in valid_coupons]

public class Solution {
    public IList<string> ValidateCoupons(string[] code, string[] businessLine, bool[] isActive) {
        var priority = new Dictionary<string, int> {
            {"electronics", 0}, {"grocery", 1}, {"pharmacy", 2}, {"restaurant", 3}
        };
        
        var validCoupons = new List<(int priority, string code)>();
        
        for (int i = 0; i < code.Length; i++) {
            if (!isActive[i]) continue;
            if (string.IsNullOrEmpty(code[i])) continue;
            if (!priority.ContainsKey(businessLine[i])) continue;
            
            bool validCode = true;
            foreach (char c in code[i]) {
                if (!char.IsLetterOrDigit(c) && c != '_') {
                    validCode = false;
                    break;
                }
            }
            
            if (validCode) {
                validCoupons.Add((priority[businessLine[i]], code[i]));
            }
        }
        
        validCoupons.Sort((a, b) => {
            if (a.priority != b.priority) return a.priority.CompareTo(b.priority);
            return a.code.CompareTo(b.code);
        });
        
        return validCoupons.Select(coupon => coupon.code).ToList();
    }
}

var validateCoupons = function(code, businessLine, isActive) {
    const priority = {"electronics": 0, "grocery": 1, "pharmacy": 2, "restaurant": 3};
    
    const validCoupons = [];
    
    for (let i = 0; i < code.length; i++) {
        if (!isActive[i]) continue;
        if (!code[i]) continue;
        if (!(businessLine[i] in priority)) continue;
        
        const validCode = /^[a-zA-Z0-9_]+$/.test(code[i]);
        
        if (validCode) {
            validCoupons.push([priority[businessLine[i]], code[i]]);
        }
    }
    
    validCoupons.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        return a[1].localeCompare(b[1]);
    });
    
    return validCoupons.map(coupon => coupon[1]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × L + m log m)n 为优惠券数量，L 为代码平均长度，m 为有效优惠券数量
空间复杂度O(m)存储有效优惠券的空间