algoadvance

Leetcode 2942. Find Words Containing Character

Problem Statement

You are given an array of strings words and a character ch. A string in words is considered containing ch if the character is present in the string.

Return an array of all the strings in words that contain the character ch.

Clarifying Questions

1. Input Format:
   • Is words guaranteed to be a non-empty array of strings?
   • Can the character ch be any valid character including whitespace and special characters?
   • What should be the output if no strings contain the character ch?
2. Output Format:
   • Should the output array maintain the order of input strings in words?

Strategy

1. Input Parsing and Edge Case Handling:
   • Ensure the input is not an empty list of words.
   • Handle edge cases where ch is not present in any string within words.
2. Filtering:
   • Traverse the list words and for each word, check if ch is present.
   • If ch is found in the word, include it in the result list.
3. Output the Result:
   • Return the list of words that contain the character ch.

Time Complexity

• Time Complexity: O(n * m), where n is the number of words in the list and m is the average length of the words. This complexity arises because we may need to check each character of each word.
• Space Complexity: O(p), where p is the total length of the words that contain the character ch.

Code

#include <vector>
#include <string>

using namespace std;

vector<string> findWordsContainingCharacter(vector<string>& words, char ch) {
    vector<string> result;
    for (const string& word : words) {
        // Check if the character `ch` is in the word
        if (word.find(ch) != string::npos) {
            result.push_back(word);
        }
    }
    return result;
}

Explanation

Here’s a breakdown of the code:

1. Check Each Word:
   • A loop iterates over the list of words.
   • For each word, word.find(ch) != string::npos checks if the character ch is present in the word.
2. Add to Result:
   • If the character ch is found in the word, it is added to the result list.
3. Return Result:
   • The function returns the result list containing all words that have the character ch.

This approach ensures that we efficiently filter out the required words while maintaining simplicity and readability.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?