Problem Description

You are given an array of strings words (0-indexed) and a character x.

Your task is to find all the indices of words in the array that contain the character x.

For example, if words = ["hello", "world", "leetcode"] and x = "o", you would return [0, 1] because:

• words[0] = "hello" contains the character "o"
• words[1] = "world" contains the character "o"
• words[2] = "leetcode" does not contain the character "o"

The returned array of indices can be in any order.

The solution uses a list comprehension to iterate through the array with enumerate(), which provides both the index i and the word w. For each word, it checks if the character x exists in the word using the in operator. If x is found in the word, the index i is included in the result list.

Intuition

The problem asks us to find which words contain a specific character. This is a straightforward filtering task where we need to check each word individually.

The natural approach is to examine every word in the array since we have no way to know which words contain the character x without checking them all. As we go through each word, we need to track two things: the word itself and its position (index) in the array, because we need to return the indices, not the words.

For checking if a character exists in a string, Python provides the in operator which efficiently searches through the string. This gives us a simple condition: if x in word is true, we want to remember that word's index.

Since we need to collect multiple indices (potentially all of them if every word contains x), we build a list of results. Python's list comprehension provides a clean way to combine the iteration, checking, and collection steps into a single line: [i for i, w in enumerate(words) if x in w].

The enumerate() function is perfect here because it gives us both the index and the word simultaneously, eliminating the need to manually track indices with a counter variable. This leads to cleaner, more readable code compared to using a traditional for loop with manual index tracking.

Solution Approach

The solution uses a direct traversal approach to examine each string in the array.

We iterate through the string array words using enumerate(), which provides both the index i and the word w at each position. This eliminates the need for manual index tracking.

For each word w at index i, we check if the character x appears in it using Python's in operator. The expression x in w returns True if the character x is found anywhere within the string w, and False otherwise.

When the condition x in w evaluates to True, we include the current index i in our result list. This is accomplished through a list comprehension that combines the iteration and filtering into a single expression: [i for i, w in enumerate(words) if x in w].

The algorithm processes each word exactly once, checking for the presence of character x. The time complexity is O(n * m) where n is the number of words and m is the average length of each word (since checking if a character exists in a string requires examining the string's characters). The space complexity for the output is O(k) where k is the number of words containing the character x.

The beauty of this solution lies in its simplicity - it directly implements what the problem asks for without any unnecessary complications. The list comprehension makes the code concise while maintaining readability.

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Example Input:

• words = ["abc", "bcd", "aaaa", "cbc"]
• x = "a"

Step-by-step execution:

Using the list comprehension [i for i, w in enumerate(words) if x in w]:

1. First iteration: i = 0, w = "abc"

   • Check: Is "a" in "abc"? → Yes (at position 0)
   • Action: Include index 0 in result

2. Second iteration: i = 1, w = "bcd"

   • Check: Is "a" in "bcd"? → No
   • Action: Skip this index

3. Third iteration: i = 2, w = "aaaa"

   • Check: Is "a" in "aaaa"? → Yes (multiple occurrences)
   • Action: Include index 2 in result

4. Fourth iteration: i = 3, w = "cbc"

   • Check: Is "a" in "cbc"? → No
   • Action: Skip this index

Final Result: [0, 2]

The indices 0 and 2 are returned because:

• words[0] = "abc" contains the character "a"
• words[2] = "aaaa" contains the character "a"

Note that even though "aaaa" contains multiple occurrences of "a", we only need to know that it contains the character (at least once), so index 2 is included just once in our result.

Solution Implementation

Time and Space Complexity

Time Complexity: O(L), where L is the sum of the lengths of all strings in the array words.

The algorithm iterates through each word in the words array using enumerate(). For each word w, it performs a substring search x in w to check if the character x is contained in the word. The substring search operation has a time complexity of O(len(w)) in the worst case. Since we perform this check for all words, the total time complexity is the sum of the lengths of all words, which is O(L).

Space Complexity: O(1) (excluding the output array)

The algorithm uses a list comprehension to generate the result. Apart from the output array that stores the indices of words containing x, the algorithm only uses a constant amount of extra space for the loop variables i and w. The space used by these variables does not depend on the input size. Therefore, ignoring the space consumption of the answer array, the space complexity is O(1).

If we include the output array, the space complexity would be O(k), where k is the number of words containing the character x, which in the worst case could be O(n) where n is the number of words in the input array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Type Confusion with Character vs String Input

A common pitfall occurs when the input x is assumed to be a single character but the function might receive a string with multiple characters. In Python, both single characters and strings are of type str, so x = "ab" would technically work with the current implementation but might not match the problem's intent.

Example of the issue:

words = ["hello", "world", "leetcode"]
x = "or"  # Multi-character string instead of single character
# Current code would check if "or" substring exists in words
# Returns [1] since "world" contains "or"

Solution: Add validation to ensure x is a single character:

def findWordsContaining(self, words: List[str], x: str) -> List[int]:
    # Validate that x is a single character
    if len(x) != 1:
        raise ValueError("x must be a single character")
  
    return [index for index, word in enumerate(words) if x in word]

2. Case Sensitivity Assumptions

The current solution is case-sensitive, meaning 'A' and 'a' are treated as different characters. This might lead to unexpected results if the problem requires case-insensitive matching.

Example of the issue:

words = ["Apple", "banana", "Orange"]
x = "a"
# Returns [1] only, missing "Apple" which contains 'A'

Solution for case-insensitive matching:

def findWordsContaining(self, words: List[str], x: str) -> List[int]:
    x_lower = x.lower()
    return [index for index, word in enumerate(words) if x_lower in word.lower()]

3. Empty String Edge Cases

The code doesn't explicitly handle edge cases where words might contain empty strings or where x itself might be an empty string.

Example of the issue:

words = ["hello", "", "world"]
x = ""
# Returns [0, 1, 2] since empty string is "in" every string

Solution:

def findWordsContaining(self, words: List[str], x: str) -> List[int]:
    # Handle empty character case
    if not x:
        return []
  
    # Filter out empty words if needed
    return [index for index, word in enumerate(words) if word and x in word]

4. Performance Degradation with Unicode Characters

When dealing with Unicode characters or multi-byte characters, the in operator might have different performance characteristics. While this usually isn't a problem, it's worth noting for international applications.

Solution: For consistent performance with Unicode, the implementation remains the same, but be aware that string operations on Unicode can be slower than ASCII-only operations.