Scale Engineer

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
ArrayString
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:

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:

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());    }}

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.

Solutions

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

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 →

Next problem