Find Words Containing Character

Easy

#2622Time: 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.1 company

Data structures

Array String

Companies

Deliveroo

Prompt

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 <= 50
1 <= words[i].length <= 50
x is a lowercase English letter.
words[i] consists only of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<Integer> findWordsContaining(String[] words, char x) {6        List<Integer> result = new ArrayList<>();7        for (int i = 0; i < words.length; i++) {8            if (words[i].indexOf(x) != -1) {9                result.add(i);10            }11        }12        return result;13    }14}

This logic can also be expressed functionally using Java Streams, which provides a more declarative style:

1import java.util.List;2import java.util.stream.Collectors;3import java.util.stream.IntStream;4 5class Solution {6    public List<Integer> findWordsContaining(String[] words, char x) {7        return IntStream.range(0, words.length)8                        .filter(i -> words[i].indexOf(x) != -1)9                        .boxed()10                        .collect(Collectors.toList());11    }12}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<Integer> findWordsContaining(String[] words, char x) {6        List<Integer> result = new ArrayList<>();7        for (int i = 0; i < words.length; i++) {8            String word = words[i];9            for (int j = 0; j < word.length(); j++) {10                if (word.charAt(j) == x) {11                    result.add(i);12                    break; // Character found, move to the next word13                }14            }15        }16        return result;17    }18}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ; } };

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem