点击获取AI摘要

2942. 查找包含给定字符的单词 E

给你一个下标从 0 开始的字符串数组 words 和一个字符 x 。

请你返回一个 下标数组 ，表示下标在数组中对应的单词包含字符 x 。

注意 ，返回的数组可以是 任意 顺序。

示例 1：

输入：words = [“leet”,“code”], x = “e”
输出：[0,1]
解释：“e” 在两个单词中都出现了：“leet” 和 “code” 。所以我们返回下标 0 和 1 。

示例 2：

输入：words = [“abc”,“bcd”,“aaaa”,“cbc”], x = “a”
输出：[0,2]
解释：“a” 在 “abc” 和 “aaaa” 中出现了，所以我们返回下标 0 和 2 。

示例 3：

输入：words = [“abc”,“bcd”,“aaaa”,“cbc”], x = “z”
输出：[]
解释：“z” 没有在任何单词中出现。所以我们返回空数组。

提示：

  • 1 <= words.length <= 50
  • 1 <= words[i].length <= 50
  • x 是一个小写英文字母。
  • words[i] 只包含小写英文字母。

问题分析

遍历 words 数组中的每个单词，检查该单词是否包含指定字符 x。若包含，则将对应的下标加入结果列表。

算法思路

由于 words.length ≤ 50 且每个 words[i].length ≤ 50，可直接采用最简单的暴力遍历方法：对每个单词使用 Python 的 in 或者遍历字符来判断是否出现 x。

时间复杂度

对于每个单词，检查是否包含字符需要 O(m)O(m) 时间（mm 为该单词长度）。总共 nn 个单词，故整体是 O(n×m)O(n \times m)，在最坏情况下约为 O(50⋅50)=O(2500)O(50·50)=O(2500)

空间复杂度：输出结果数组至多长度为 nn，故为 O(n)O(n)

代码分解

  1. 新建一个空列表 res 用于收集所有符合条件的下标。

  2. 遍历下标 i 从 0 到 len(words)-1：

    • 令 word = words[i]，检查字符 x 是否在 word 中。
      • 在 Python 中可以直接写 if x in word:，其底层实际上是遍历 word 的所有字符进行比较，复杂度为 O(m)。
    • 如果包含，则执行 res.append(i)。

  3. 循环结束后，返回 res（由于题目说明“返回的数组可以是 任意 顺序”，不需要对下标排序）。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findWordsContaining(self, words, x):
        """
        :type words: List[str]
        :type x: str
        :rtype: List[int]
        """
        res = []
        for i, word in enumerate(words):
            # 只要在 word 中找到 x，就把索引 i 加入结果
            if x in word:
                res.append(i)
        return res