# Find Words Containing Character
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-words-containing-character)
Canonical: https://scaleengineer.com/dsa/problems/find-words-containing-character
**Data structures:** Array, String
**Companies:** [Deliveroo](https://scaleengineer.com/companies/deliveroo)
---
## Problem
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: "l**ee**t", and "cod**e**". Hence, we return indices 0 and 1.

**Example 2:**

**Input:** words = ["abc","bcd","aaaa","cbc"], x = "a"
**Output:** [0,2]
**Explanation:** "a" occurs in "**a**bc", 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.

# Approaches
## Brute-Force with Nested Loops
This fundamental approach uses nested loops to solve the problem. The outer loop iterates through each word in the input array, and for each word, an inner loop iterates through its characters to check for the presence of the target character `x`.
**Time:** O(N * M), where `N` is the number of words in the input array and `M` is the maximum length of a word. The outer loop runs `N` times, and the inner loop runs up to `M` times for each word. · **Space:** O(K), where `K` is the number of words containing the character `x`. In the worst-case scenario (all words contain `x`), the space complexity becomes `O(N)`, where `N` is the total number of words. This space is used for the output list.
**Pros:** Straightforward and easy to understand, clearly showing the logic.; No dependency on specific library functions for string searching.
**Cons:** Slightly more verbose than using built-in methods.; May be marginally slower in practice as it doesn't leverage potential low-level optimizations of native string functions.
### Explanation
In this approach, we manually implement the search logic. We start by initializing an empty list to store the indices of the words that contain the character `x`. We then use an outer `for` loop to traverse the `words` array, keeping track of the current index `i`. Inside this loop, we have a nested `for` loop that iterates over each character of the word `words[i]`. If a character matches `x`, we add the index `i` to our result list. A small optimization is to `break` out of the inner loop as soon as a match is found, since we only need to know if the character exists in the word, not how many times it appears. This prevents unnecessary checks for the rest of the characters in that word.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findWordsContaining(String[] words, char x) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            for (int j = 0; j < word.length(); j++) {
                if (word.charAt(j) == x) {
                    result.add(i);
                    break; // Character found, move to the next word
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list of integers, `result`.
- Loop through the `words` array with an index `i` from 0 to `words.length - 1`.
- For each `word = words[i]`, start another loop to iterate through its characters with an index `j` from 0 to `word.length() - 1`.
- Inside the inner loop, check if `word.charAt(j) == x`.
- If the condition is true, add the index `i` to the `result` list.
- To avoid adding the same index multiple times, `break` the inner loop once the character is found.
- After the outer loop finishes, return the `result` list.

## Using Built-in String Method
A more efficient and idiomatic approach is to use the built-in `String.indexOf(char)` method. This method is highly optimized to find the first occurrence of a character in a string. We iterate through the words and use this method to check for the character's existence.
**Time:** O(N * M), where `N` is the number of words and `M` is the maximum length of a word. The `indexOf` method itself has a time complexity of O(M) in the worst case. · **Space:** O(K), where `K` is the number of words containing the character `x`. In the worst case, this is `O(N)`, where `N` is the total number of words. The space is required for storing the resulting list of indices.
**Pros:** More concise, readable, and idiomatic Java code.; Leverages highly optimized, often native, implementations of string searching, which can lead to better practical performance.
**Cons:** The underlying time complexity is asymptotically the same as the manual nested loop approach.
### Explanation
This approach leverages Java's built-in `String.indexOf(char)` method for a cleaner and potentially faster solution. The `indexOf` method searches for the first occurrence of a character within a string and returns its index, or `-1` if the character is not found.

We iterate through the `words` array using a single loop. For each word, we call `word.indexOf(x)`. If the returned value is not `-1`, we know the character `x` is present in the word, and we add the word's index to our result list. This method is generally preferred as it leads to more concise code and can benefit from JVM's internal optimizations for string operations.

Here is an implementation using a standard `for` loop:
```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findWordsContaining(String[] words, char x) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            if (words[i].indexOf(x) != -1) {
                result.add(i);
            }
        }
        return result;
    }
}
```

This logic can also be expressed functionally using Java Streams, which provides a more declarative style:
```java
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class Solution {
    public List<Integer> findWordsContaining(String[] words, char x) {
        return IntStream.range(0, words.length)
                        .filter(i -> words[i].indexOf(x) != -1)
                        .boxed()
                        .collect(Collectors.toList());
    }
}
```
### Algorithm
- Initialize an empty `ArrayList<Integer>` named `result`.
- Iterate through the `words` array using an index `i` from `0` to `words.length - 1`.
- For each `word` at `words[i]`, check if `word.indexOf(x)` is not equal to `-1`.
- If the condition is true (meaning the character `x` is found), add the index `i` to `result`.
- After the loop completes, return `result`.

# Solutions
### Java

```java
class Solution { public List < Integer > findWordsContaining ( String [] words , char x ) { List < Integer > ans = new ArrayList <>(); for ( int i = 0 ; i < words . length ; ++ i ) { if ( words [ i ]. indexOf ( x ) != - 1 ) { ans . add ( i ); } } return ans ; } }
```

### CPP

```cpp
class Solution { public: vector < int > findWordsContaining ( vector < string >& words , char x ) { vector < int > ans ; for ( int i = 0 ; i < words . size (); ++ i ) { if ( words [ i ]. find ( x ) != string :: npos ) { ans . push_back ( i ); } } return ans ; } };
```

### Python

```python
class Solution : def findWordsContaining ( self , words : List [ str ], x : str ) -> List [ int ]: return [ i for i , w in enumerate ( words ) if x in w ]
```