Find Words Containing Character — Easy Problem & Solution

Given an array of strings words and a single character x, return the indices of the words that contain x, in increasing order.

Difficulty: Easy
Topics: Arrays, Strings
Asked at: Amazon, Google, Capgemini
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array of strings words and a single character x, return the indices of the words that contain x, in increasing order.

Example 1

Input: words = ["code","kairo","judge"], x = "o"
Output: [0,1]
Explanation: `judge` has no `o`.

Example 2

Input: words = ["abc","bcd","aaaa","cbc"], x = "a"
Output: [0,2]

Example 3

Input: words = ["abc","bcd","aaaa","cbc"], x = "z"
Output: []
Explanation: No word contains `z`.

Constraints

1 <= words.length <= 50
1 <= words[i].length <= 50
x is a lowercase English letter.
words[i] consists only of lowercase English letters.

How to solve Find Words Containing Character

A single pass: for each index, if the word contains x, record the index.

Approach

Iterate over words with its index.
Test membership of x with a substring search or a character loop.
Append the index to the result when found.

Why it works

Scanning in index order is what makes the output sorted for free — no sort is needed. The only thing to be careful about is returning an empty array rather than null when nothing matches, which some judges treat differently.

Complexity

Time — O(n · m)
Space — O(n) for the output

Pitfalls

Return indices, not the words themselves.
An empty answer must still be an array.
A word containing x several times is still recorded once.

Reference solution

Python

from typing import List

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

JavaScript

var findWordsContaining = function(words, x) {
    var out = [];
    for (var i = 0; i < words.length; i++) {
        if (words[i].indexOf(x) !== -1) out.push(i);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue