How can I solve the Count Items Matching a Rule problem efficiently?

Iterate through the array and use conditional checks to match the rule based on the ruleKey and ruleValue. Optimize by reducing redundant checks and using direct index access.

What is the time complexity of the Count Items Matching a Rule problem?

The time complexity is O(n), where n is the number of items, as you iterate through the list once.

What happens if no items match the rule in Count Items Matching a Rule?

The function will return 0, indicating no items matched the given rule.

How do I handle larger inputs in Count Items Matching a Rule?

To handle large inputs efficiently, optimize the iteration by minimizing unnecessary checks and using index mappings instead of string comparisons.

What are the edge cases for Count Items Matching a Rule?

Edge cases include empty arrays, items where no element matches the rule, and scenarios where the ruleKey is not valid or does not match any items.

#1773

Easy

auto_awesome数组·string

LeetCode 题解工作台

统计匹配检索规则的物品数量

给你一个数组 items ，其中 items[i] = [type i , color i , name i ] ，描述第 i 件物品的类型、颜色以及名称。另给你一条由两个字符串 ruleKey 和 ruleValue 表示的检索规则。如果第 i 件物品能满足下述条件之一，则认为该物品与给定的检…

数组字符串

题目描述

给你一个数组 items ，其中 items[i] = [type_i, color_i, name_i] ，描述第 i 件物品的类型、颜色以及名称。

另给你一条由两个字符串 ruleKey 和 ruleValue 表示的检索规则。

如果第 i 件物品能满足下述条件之一，则认为该物品与给定的检索规则匹配：

ruleKey == "type" 且 ruleValue == type_i 。
ruleKey == "color" 且 ruleValue == color_i 。
ruleKey == "name" 且 ruleValue == name_i 。

统计并返回 匹配检索规则的物品数量 。

示例 1：

输入：items = [["phone","blue","pixel"],["computer","silver","lenovo"],["phone","gold","iphone"]], ruleKey = "color", ruleValue = "silver"
输出：1
解释：只有一件物品匹配检索规则，这件物品是 ["computer","silver","lenovo"] 。

示例 2：

输入：items = [["phone","blue","pixel"],["computer","silver","phone"],["phone","gold","iphone"]], ruleKey = "type", ruleValue = "phone"
输出：2
解释：只有两件物品匹配检索规则，这两件物品分别是 ["phone","blue","pixel"] 和 ["phone","gold","iphone"] 。注意，["computer","silver","phone"] 未匹配检索规则。

提示：

1 <= items.length <= 10⁴
1 <= type_i.length, color_i.length, name_i.length, ruleValue.length <= 10
ruleKey 等于 "type"、"color" 或 "name"
所有字符串仅由小写字母组成

lightbulb

解题思路

方法一：计数模拟

由于 ruleKey 只可能是 "type"、"color" 或 "name"，我们可以直接取 ruleKey 的第一个字符来确定 item 的下标 $i$ 。然后遍历 items 数组，统计 item[i] == ruleValue 的个数即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为 items 的长度。

1

2

3

4

5

class Solution:
    def countMatches(self, items: List[List[str]], ruleKey: str, ruleValue: str) -> int:
        i = 0 if ruleKey[0] == 't' else (1 if ruleKey[0] == 'c' else 2)
        return sum(v[i] == ruleValue for v in items)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate should understand how to iterate over arrays and conditionally check string values.
question_mark
Look for the ability to optimize iterations, such as reducing unnecessary string comparisons.
question_mark
See if the candidate can efficiently handle larger input sizes through improved algorithms.

warning

常见陷阱

外企场景

error
Failing to properly match ruleKey to the correct index in the item array, leading to incorrect results.
error
Not handling edge cases like empty arrays or rules that don't match any item.
error
Unnecessarily complex solutions that don't take advantage of simple iteration for this problem.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the ruleKey is dynamic and changes per item, requiring different ruleKey checks for each one?
arrow_right_alt
Consider a variant where you need to count multiple types of rules in one pass, instead of just one rule.
arrow_right_alt
Change the input so that the ruleValue is not a string but a more complex data structure, like a range or set.

help

常见问题

外企场景

继续练习

#1769 移动所有球到每个盒子所需的最小操作数 #1807 替换字符串中的括号内容 #1813 句子相似性 III