Find Words Containing Character

EASY

Description

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

Checkout 2 different approaches to solve Find Words Containing Character. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find Words Containing Character. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Find Words Containing Character

Data Structures:

ArrayString

Companies:

Deliveroo |