Problem Informations

• Problem Index: 2942
• Problem Link: Find Words Containing Character
• Topics: Array, String

Problem 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 \leq \text{words.length} \leq 50$
• $1 \leq \text{words}[i].\text{length} \leq 50$
• $x$ is a lowercase English letter.
• $\text{words}[i]$ consists only of lowercase English letters.

Intuition

The problem requires us to identify which strings in a given array of words contain a specified character. The task naturally leads to an iterative approach where each word is examined to check for the presence of the target character. Given the constraints, a straightforward approach would be efficient enough and should suffice to solve the problem.

Approach

The solution employs a linear search strategy which inspects each word in the array to determine if it contains the specified character. Here is a step-by-step breakdown of the approach:

1. Define a Helper Function: A private helper function containsCharacter is defined, which checks whether a given character exists within a specific string. This function iterates over each character of the string and returns true if the target character is found, otherwise false.

2. Iterate Over Words: Within the public method findWordsContaining, we initialize an empty vector result to store the indices of words that contain the target character.

3. Check Each Word: We iterate over the list of words using an index i. For each word, we utilize the containsCharacter function to ascertain if the word includes the specified character x.

4. Store Indices: If a word contains the character, we append the current index i to the result vector using emplace_back.

5. Return the Result: After the loop completes, the result vector, which contains the indices of all words containing the character, is returned.

This approach effectively navigates through each word and checks for the character, adhering to a time complexity of (O(n \cdot m)), where (n) is the number of words and (m) is the average length of the words, which is efficient given the problem constraints.

Code

C++

class Solution {
private:
    // Checks if the character c exists within the string str
    bool containsCharacter(const string& str, char c) {
        for (char s : str) {
            if (s == c) {
                return true;
            }
        }
        return false;
    }
    
public:
    // Finds and returns indices of words that contain the character x
    vector<int> findWordsContaining(vector<string>& words, char x) {
        int len = words.size();
        vector<int> result;
        
        for (int i = 0; i < len; i++) {
            if (containsCharacter(words[i], x)) {
                result.emplace_back(i);
            }
        }
        
        return result;
    }
};

Python

class Solution:
    # Checks if the character c exists within the string str
    def containsCharacter(self, str, c):
        for s in str:
            if s == c:
                return True
        return False

    # Finds and returns indices of words that contain the character x
    def findWordsContaining(self, words, x):
        len_words = len(words)
        result = []
        
        for i in range(len_words):
            if self.containsCharacter(words[i], x):
                result.append(i)
        
        return result

Complexity

• Time complexity: $O(n \cdot m)$
  The time complexity is $O(n \cdot m)$, where $n$ is the number of words in the input array, and $m$ is the maximum length of a word. This is because for each word in the words array, the containsCharacter function iterates through each character in the word to check for the existence of the character x.
• Space complexity: $O(n)$
  The space complexity is $O(n)$, where $n$ is the number of words. This is due to the result vector which, in the worst case, could potentially store the index of every word in the words array if all words contain the character x.