Skip to main content
Talentd

Find Words Containing Character - Solution & Explanation

EasyArrayString11 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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 <= 50
  • 1 <= words[i].length <= 50
  • x is a lowercase English letter.
  • words[i] consists only of lowercase English letters.

Approach Overview

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.

Approach 1: Iterative Approach

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.

Code

PythonJavaCC++C#JavaScript

Python

Java

C

C++

C#

JavaScript

Complexity

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'.

Try this approach in the editor →

Approach 2: Set-Based Approach

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.

Code

PythonJavaJavaScript

Python

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Traversal

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).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Approach

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'.

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.
Space Complexity: O(k + m), where k is the number of words containing 'x' and m is the memory necessary for character set conversion.

Traversal—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative ScanO(n * m)O(1)Best general solution. Minimal memory usage and simplest logic for scanning words.
Set-Based Character LookupO(n * m)O(m)Useful when multiple membership checks are needed for each word or when demonstrating hash-set lookups.

Video Solution

Find words containing character | Leetcode 2942 • Technosage • 4,423 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Words Containing Character easy or hard?
Find Words Containing Character is classified as an Easy problem on LeetCode with a very high acceptance rate. It focuses on basic array iteration and string membership checks rather than complex algorithms.
Find Words Containing Character Python/Java solution
In Python, iterate through the list and append the index if x in word. In Java, use a loop and check word.indexOf(x) != -1 or word.contains(String.valueOf(x)). Both implementations run in O(n * m) time and store the resulting indices in a list.
How to solve Find Words Containing Character in O(n)?
Strict O(n) is only possible if string membership checks are treated as constant time by the language runtime. In practice the algorithm scans characters inside each word, resulting in O(n * m) time. The standard solution iterates through words and checks whether the character exists in each string.
What is the best approach for Find Words Containing Character?
The iterative scan approach is the best solution. Traverse the words array and check if each string contains the target character. This runs in O(n * m) time where n is the number of words and m is the average word length, while using O(1) extra space.
Is Find Words Containing Character asked at Google/Amazon/Meta?
Problems of this type appear frequently in screening rounds because they test basic string traversal and indexing logic. While this exact question is considered easy, variations involving string filtering or character matching appear in interviews at companies like Amazon and Google.
What data structure is used in Find Words Containing Character?
The primary structures are arrays (for the list of words) and strings. Some implementations also use a hash set to store characters of a word for O(1) membership checks, though the simplest approach just scans the string directly.
What is the time complexity of Find Words Containing Character?
The time complexity is O(n * m). You must examine each word and potentially each character inside that word. Here n is the number of strings and m is the average length of a string.

Ready to solve this problem?

Practice Find Words Containing Character with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Target Indices After Sorting Array