LeetCode 2942 - Find Words Containing Character

LeetCode Problem 2942

Difficulty: 🟢 Easy
Topics: Array, String

Solution

Problem Understanding

The problem asks us to process an array of lowercase strings words and a single lowercase character x, and return all indices of the words that contain this character. In simpler terms, for each string in the array, we must check whether x appears anywhere in that string. If it does, we record the index of that word. The order of the returned indices does not matter, giving some flexibility in implementation.

The input constraints are small: words can have up to 50 elements, and each word can be up to 50 characters long. The character x is guaranteed to be a single lowercase English letter. These constraints indicate that even simple approaches with nested iteration over words and their characters are feasible in practice.

Important edge cases to keep in mind include scenarios where no word contains x (returning an empty list), all words contain x (returning all indices), and x appearing multiple times within a word (which should still count as a single inclusion).

Approaches

The most straightforward approach is brute force: iterate over each word, check each character of the word, and if any character matches x, record the index. This works because the input size is small, but it is slightly inefficient since we might check more characters than necessary.

A slightly more efficient approach leverages built-in string membership checking, which is usually implemented in C and highly optimized. This lets us check whether x is in a word in a single operation rather than manually iterating over each character.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(n)	Iterate each word and each character manually; record indices when match found
Optimal	O(n * m)	O(n)	Use built-in string containment checks to simplify and optimize iteration

Here, n is the number of words and m is the maximum length of a word. Both approaches require storing the indices of matches, giving O(n) additional space.

Algorithm Walkthrough

1. Initialize an empty list result to store indices of words that contain x.
2. Iterate over the array words using a loop with index i.
3. For each word words[i], check if the character x exists in the word.
4. If x is present, append the index i to the result list.
5. After iterating through all words, return the result list.

Why it works: By checking each word for the presence of x and collecting the corresponding indices, we ensure that every word containing x is represented in the output. Since we process each word independently, no valid index is missed, and duplicates are avoided because we only store indices, not multiple occurrences.

Python Solution

from typing import List

class Solution:
    def findWordsContaining(self, words: List[str], x: str) -> List[int]:
        result = []
        for i, word in enumerate(words):
            if x in word:
                result.append(i)
        return result

Explanation: We use enumerate to get both the index and the word while iterating. The if x in word check leverages Python's efficient built-in string membership operation. If a match is found, we append the index to result. Finally, we return the list of indices after processing all words.

Go Solution

func findWordsContaining(words []string, x byte) []int {
    var result []int
    for i, word := range words {
        for j := 0; j < len(word); j++ {
            if word[j] == x {
                result = append(result, i)
                break
            }
        }
    }
    return result
}

Go-specific notes: Go does not support a direct string membership operation like Python, so we manually iterate over the bytes of each word. We break the inner loop as soon as we find a match to avoid unnecessary iterations. Using []int ensures a dynamically sized slice to store results efficiently.

Worked Examples

Example 1: words = ["leet","code"], x = "e"

Step	Word	Contains 'e'?	Result
0	"leet"	Yes	[0]
1	"code"	Yes	[0,1]

Output: [0,1]

Example 2: words = ["abc","bcd","aaaa","cbc"], x = "a"

Step	Word	Contains 'a'?	Result
0	"abc"	Yes	[0]
1	"bcd"	No	[0]
2	"aaaa"	Yes	[0,2]
3	"cbc"	No	[0,2]

Output: [0,2]

Example 3: words = ["abc","bcd","aaaa","cbc"], x = "z"

Step	Word	Contains 'z'?	Result
0	"abc"	No	[]
1	"bcd"	No	[]
2	"aaaa"	No	[]
3	"cbc"	No	[]

Output: []

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * m)	Iterate each of the n words, and for each word of length m, check for presence of x
Space	O(n)	Store indices of words containing x; worst case all words match

The algorithm is efficient given the constraints (n ≤ 50, m ≤ 50) and scales linearly with the number of words and characters.

Test Cases

# test cases
sol = Solution()

# example cases
assert sol.findWordsContaining(["leet","code"], "e") == [0,1]  # both contain 'e'
assert sol.findWordsContaining(["abc","bcd","aaaa","cbc"], "a") == [0,2]  # indices 0 and 2
assert sol.findWordsContaining(["abc","bcd","aaaa","cbc"], "z") == []  # none contain 'z'

# boundary cases
assert sol.findWordsContaining(["a"], "a") == [0]  # single word, single letter, match
assert sol.findWordsContaining(["b"], "a") == []  # single word, single letter, no match
assert sol.findWordsContaining(["abc","abc","abc"], "c") == [0,1,2]  # repeated words

# multiple occurrences
assert sol.findWordsContaining(["aa","ab","ba"], "a") == [0,1,2]  # multiple 'a's per word

# all words contain character
assert sol.findWordsContaining(["abc","ac","a"], "a") == [0,1,2]  # all match

Test	Why
example cases	verify correctness against problem statement
single word	check smallest input sizes
repeated words	check handling of multiple identical words
multiple occurrences	ensure repeated letters do not affect index collection
all match	verify all indices are returned when all words contain x

Edge Cases

One important edge case is when no word contains x. In this scenario, the correct output is an empty list or slice. This could be a source of bugs if one mistakenly initializes the result list with default values or forgets to handle the empty case. Our solution naturally returns an empty list when no matches are found.

Another edge case occurs when every word contains the character x. The algorithm must correctly return all indices, not just a subset. Using append in Python or Go ensures that all matching indices are captured dynamically.

A third edge case is when x appears multiple times in the same word. It is crucial that we only record the index once. Both Python's in operation and the Go break after a match handle this correctly by terminating the check for that word once a match is found, preventing duplicate indices.