Watch 10 video solutions for Find Words Containing Character, a easy level problem involving Array, String. This walkthrough by Technosage has 4,075 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |