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

题目链接

2942. 查找包含给定字符的单词 - 力扣（LeetCode）

题目描述

给你一个下标从 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 。

解题思路

1. 问题描述：给定一个字符串数组words和一个字符x，找出所有包含字符x的单词的索引，并将这些索引存入一个列表返回。
2. 核心思路：
   • 遍历数组：逐个检查数组中的每个单词是否包含目标字符x。
   • 检查字符存在性：使用String.indexOf(char)方法判断字符x是否存在于当前单词中。如果返回值 ≥ 0，说明字符存在。
   • 记录索引：如果字符存在，则将当前单词的索引添加到结果列表中。
3. 关键点：
   • String.indexOf(char)方法是关键，它直接判断字符是否存在于字符串中。
   • 结果列表动态增长，使用ArrayList可以高效地添加元素。

题解代码

classSolution{publicList<Integer>findWordsContaining(String[]words,charx){// 创建一个ArrayList来存储结果，保存包含字符x的单词的索引List<Integer>ans=newArrayList<>();// 遍历words数组中的每一个单词for(inti=0;i<words.length;i++){// 检查当前单词words[i]是否包含字符x// indexOf方法返回字符x在单词中的位置，如果不存在则返回-1if(words[i].indexOf(x)>=0){// 如果包含字符x，则将当前单词的索引i添加到结果列表中ans.add(i);}}// 返回结果列表returnans;}}

复杂度分析

1. 时间复杂度：O(n * m)
   • n是words数组的长度，m是数组中单词的平均长度。
   • 需要遍历每个单词（O(n)），对于每个单词，indexOf方法需要检查每个字符（O(m)）。
   • 因此，总时间复杂度为 O(n * m)。
2. 空间复杂度：O(k)
   • k是结果列表ans中存储的索引数量（即包含字符x的单词数量）。
   • 最坏情况下，所有单词都包含x，此时k = n，空间复杂度为 O(n)。
   • 一般情况下，空间复杂度取决于匹配的单词数量。