3606. 优惠券校验器

题目描述

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

• 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"。
• 在每个类别内，再按照 标识符的字典序（升序）排序。

 

示例 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. 检查标识符：对于每个优惠券的标识符，检查它是否非空，并且只包含字母、数字和下划线。
2. 检查业务类别：检查每个优惠券的业务类别是否属于给定的四个有效类别之一。
3. 检查激活状态：检查每个优惠券是否处于激活状态。
4. 收集有效优惠券：将所有满足上述条件的优惠券的 id 收集起来。
5. 排序：根据业务类别和标识符对有效优惠券进行排序。
6. 返回结果：返回排序后的有效优惠券的标识符列表。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(n)\)，其中 \(n\) 是优惠券的数量。

Python3JavaC++GoTypeScript

class Solution:
    def validateCoupons(
        self, code: List[str], businessLine: List[str], isActive: List[bool]
    ) -> List[str]:
        def check(s: str) -> bool:
            if not s:
                return False
            for c in s:
                if not (c.isalpha() or c.isdigit() or c == "_"):
                    return False
            return True

        idx = []
        bs = {"electronics", "grocery", "pharmacy", "restaurant"}
        for i, (c, b, a) in enumerate(zip(code, businessLine, isActive)):
            if a and b in bs and check(c):
                idx.append(i)
        idx.sort(key=lambda i: (businessLine[i], code[i]))
        return [code[i] for i in idx]

class Solution {
    public List<String> validateCoupons(String[] code, String[] businessLine, boolean[] isActive) {
        List<Integer> idx = new ArrayList<>();
        Set<String> bs
            = new HashSet<>(Arrays.asList("electronics", "grocery", "pharmacy", "restaurant"));

        for (int i = 0; i < code.length; i++) {
            if (isActive[i] && bs.contains(businessLine[i]) && check(code[i])) {
                idx.add(i);
            }
        }

        idx.sort((i, j) -> {
            int cmp = businessLine[i].compareTo(businessLine[j]);
            if (cmp != 0) {
                return cmp;
            }
            return code[i].compareTo(code[j]);
        });

        List<String> ans = new ArrayList<>();
        for (int i : idx) {
            ans.add(code[i]);
        }
        return ans;
    }

    private boolean check(String s) {
        if (s.isEmpty()) {
            return false;
        }
        for (char c : s.toCharArray()) {
            if (!Character.isLetterOrDigit(c) && c != '_') {
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    vector<string> validateCoupons(vector<string>& code, vector<string>& businessLine, vector<bool>& isActive) {
        vector<int> idx;
        unordered_set<string> bs = {"electronics", "grocery", "pharmacy", "restaurant"};

        for (int i = 0; i < code.size(); ++i) {
            const string& c = code[i];
            const string& b = businessLine[i];
            bool a = isActive[i];
            if (a && bs.count(b) && check(c)) {
                idx.push_back(i);
            }
        }

        sort(idx.begin(), idx.end(), [&](int i, int j) {
            if (businessLine[i] != businessLine[j]) return businessLine[i] < businessLine[j];
            return code[i] < code[j];
        });

        vector<string> ans;
        for (int i : idx) {
            ans.push_back(code[i]);
        }
        return ans;
    }

private:
    bool check(const string& s) {
        if (s.empty()) return false;
        for (char c : s) {
            if (!isalnum(c) && c != '_') {
                return false;
            }
        }
        return true;
    }
};

func validateCoupons(code []string, businessLine []string, isActive []bool) []string {
    idx := []int{}
    bs := map[string]struct{}{
        "electronics": {},
        "grocery":     {},
        "pharmacy":    {},
        "restaurant":  {},
    }

    check := func(s string) bool {
        if len(s) == 0 {
            return false
        }
        for _, c := range s {
            if !unicode.IsLetter(c) && !unicode.IsDigit(c) && c != '_' {
                return false
            }
        }
        return true
    }

    for i := range code {
        if isActive[i] {
            if _, ok := bs[businessLine[i]]; ok && check(code[i]) {
                idx = append(idx, i)
            }
        }
    }

    sort.Slice(idx, func(i, j int) bool {
        if businessLine[idx[i]] != businessLine[idx[j]] {
            return businessLine[idx[i]] < businessLine[idx[j]]
        }
        return code[idx[i]] < code[idx[j]]
    })

    ans := make([]string, 0, len(idx))
    for _, i := range idx {
        ans = append(ans, code[i])
    }
    return ans
}

function validateCoupons(code: string[], businessLine: string[], isActive: boolean[]): string[] {
    const idx: number[] = [];
    const bs = new Set(['electronics', 'grocery', 'pharmacy', 'restaurant']);

    const check = (s: string): boolean => {
        if (s.length === 0) return false;
        for (let i = 0; i < s.length; i++) {
            const c = s[i];
            if (!/[a-zA-Z0-9_]/.test(c)) {
                return false;
            }
        }
        return true;
    };

    for (let i = 0; i < code.length; i++) {
        if (isActive[i] && bs.has(businessLine[i]) && check(code[i])) {
            idx.push(i);
        }
    }

    idx.sort((i, j) => {
        if (businessLine[i] !== businessLine[j]) {
            return businessLine[i] < businessLine[j] ? -1 : 1;
        }
        return code[i] < code[j] ? -1 : 1;
    });

    return idx.map(i => code[i]);
}

评论