You are given a 0-indexed array of strings words and a character x.
Return an array of indices representing the words that contain the character x.
Note that the returned array may be in any order.
Example 1:
Input: words = ["leet","code"], x = "e" Output: [0,1] Explanation: "e" occurs in both words: "leet", and "code". Hence, we return indices 0 and 1.
Example 2:
Input: words = ["abc","bcd","aaaa","cbc"], x = "a" Output: [0,2] Explanation: "a" occurs in "abc", and "aaaa". Hence, we return indices 0 and 2.
Example 3:
Input: words = ["abc","bcd","aaaa","cbc"], x = "z" Output: [] Explanation: "z" does not occur in any of the words. Hence, we return an empty array.
Constraints:
1 <= words.length <= 501 <= words[i].length <= 50x is a lowercase English letter.words[i] consists only of lowercase English letters.Problem Overview: You receive an array of strings words and a character x. The task is to return the indices of all words that contain this character at least once. The output keeps the original order of indices from the array.
Approach 1: Iterative Scan (O(n * m) time, O(1) extra space)
The most direct solution is to iterate through each word and check whether the target character exists inside it. For every index i, scan the characters of words[i]. If any character equals x, add the index to the result list. The operation is simple: an outer loop over the array and an inner character check using either a manual loop or built‑in string search like in (Python) or contains (Java). If there are n words and the average word length is m, the total work becomes O(n * m). The approach uses constant extra space because it only stores the output indices. This solution relies purely on sequential scanning and works well for typical array and string traversal problems.
Approach 2: Set-Based Character Lookup (O(n * m) time, O(m) space per word)
Another option converts each word into a set of characters and checks whether x exists in that set. Building a set for a word takes O(m), and the membership check runs in average O(1) time thanks to hashing. This approach uses a HashSet (or Python set) to speed up repeated lookups when multiple character checks might be required. In this specific problem we only check one character, so the overall complexity remains O(n * m), with additional memory overhead of up to O(m) per word. It mainly demonstrates how hashing structures from hash table concepts can accelerate membership queries.
Recommended for interviews: The iterative scan is what interviewers expect. It shows you recognize the simplest correct solution and understand string traversal. The set-based approach is useful if the problem evolves to checking multiple characters or performing frequent membership queries. Demonstrating the basic scan first proves clarity of thought; mentioning the set optimization shows awareness of hashing tradeoffs.
This approach involves iterating through each word in the array and checking if the character 'x' is present in the word. We simply append the index of the word to our result list if the character is found. The iteration through each word makes this a straightforward and easy-to-understand approach.
The code uses a list comprehension combined with the enumerate function to loop over each word in the 'words' list, checking if 'x' is in each word. If so, it collects the index 'i' into the resulting list.
Time Complexity: O(n * m), where n is the number of words and m is the average length of a word.
Space Complexity: O(k), where k is the number of words that contain the character 'x'.
This approach involves converting each word into a set of characters and checking if 'x' is present in the set. The advantage of using sets is that it allows for efficient membership testing, leading to more readable code specifically in languages that offer easy set manipulations.
In this Python solution, each word is converted to a set of characters before checking if 'x' is in the set. We use a list comprehension to efficiently create the list of indices for words where 'x' is found.
Python
Java
JavaScript
Time Complexity: O(n * m), where n is the number of words and m is the average number of distinct characters in a word.
Space Complexity: O(k + m), where k is the number of words containing 'x' and m is the memory necessary for character set conversion.
We directly traverse each string words[i] in the string array words. If x appears in words[i], we add i to the answer array.
After the traversal, we return the answer array.
The time complexity is O(L), where L is the sum of the lengths of all strings in the array words. Ignoring the space consumption of the answer array, the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n * m), where n is the number of words and m is the average length of a word. |
| Set-Based Approach | Time Complexity: O(n * m), where n is the number of words and m is the average number of distinct characters in a word. |
| Traversal | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Scan | O(n * m) | O(1) | Best general solution. Minimal memory usage and simplest logic for scanning words. |
| Set-Based Character Lookup | O(n * m) | O(m) | Useful when multiple membership checks are needed for each word or when demonstrating hash-set lookups. |
Find words containing character | Leetcode 2942 • Technosage • 4,075 views views
Watch 9 more video solutions →Practice Find Words Containing Character with our built-in code editor and test cases.
Practice on FleetCode