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.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.
Java
C
C++
C#
JavaScript
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.
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.
| 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. |
Word Search - Backtracking - Leetcode 79 - Python • NeetCode • 380,746 views views
Watch 9 more video solutions →Practice Find Words Containing Character with our built-in code editor and test cases.
Practice on FleetCode