Jobs

Interviews

Discussions

Find Words Containing Character

Easy

Asked by:

More companies

76 views

Topics:

ArraysStrings

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.

Try coding it in LeetCode

Find Words Containing Character

Easy

Asked by:

76 views

Topics:

ArraysStrings

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input `words` array contain null or empty strings?
Is the `character` a single character, or could it be a string of multiple characters?
Is the `character` case-sensitive? Should I consider case-insensitive matching?
What should be returned if none of the words contain the specified character? An empty array?
Are there any limitations on the length of individual words within the `words` array?

Brute Force Solution

Approach

The brute-force approach involves going through each word in the provided list. For every word, we simply check if the target character is present within that word.

Here's how the algorithm would work step-by-step:

Take the first word from the list.
Look at each letter in the word to see if any of them match the character we're searching for.
If we find a match, remember the position of that word in the original list.
Move on to the next word in the list and repeat the process of checking each letter.
Keep repeating this process until we have checked every single word in the list.
Finally, provide a list of all the positions where we found words containing the specified character.

Code Implementation

def find_words_containing_character(words, character):
    indices_of_matching_words = []

    for word_index in range(len(words)):
        word = words[word_index]

        # Iterate through each character to find match
        for char_index in range(len(word)):
            if word[char_index] == character:

                # Store index because the word contains char
                indices_of_matching_words.append(word_index)

                break

    # Return all of the word indices that match
    return indices_of_matching_words

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through each of the n words in the input list. For each word, it iterates through each of the m characters in that word to check if the target character is present. Therefore, the time complexity is proportional to the product of the number of words and the average length of each word. This results in a time complexity of O(n*m), where n is the number of words and m is the average word length.

Space Complexity

O(K) – The provided algorithm iterates through a list of words and for each word, checks if a given character is present. The key space usage arises from storing the indices of the words containing the character, as described in step 6. In the worst-case scenario, every word in the input list contains the character, requiring us to store the index of each word. Thus, if the input list contains N words, we might store up to N indices. Therefore, the auxiliary space complexity is O(K) where K is the number of words containing the target character; In the worst case where all words contain the target character, K=N.

Optimal Solution

Approach

The goal is to identify all the words in a list that include a specific character. Instead of complex searching, the best way is to simply check each word individually. This guarantees we find all matching words quickly and accurately.

Here's how the algorithm would work step-by-step:

Take the first word from the list.
Check if the specific character is present anywhere in that word.
If the character is present, save that word to a separate list of 'found' words.
Repeat this process for every word in the original list.
Once you've checked all the words, the separate list contains all the words that include the specific character.

Code Implementation

def find_words_containing_character(words, character):
    words_containing_char = []

    # Iterate through each word in the input list
    for word in words:
        # Check if the character is present in the current word
        if character in word:

            # Add the word to result if the character is found
            words_containing_char.append(word)

    return words_containing_char

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through each of the n words in the input list. For each word, it checks if the given character is present. In the worst-case scenario, it might have to iterate through all m characters of that word to determine if the character exists within it. Thus, the overall time complexity is O(n*m), where n is the number of words and m is the maximum length of a single word.

Space Complexity

O(N) – The algorithm creates a new list, 'found' words, to store words containing the specific character. In the worst-case scenario, where every word in the original list contains the character, the 'found' words list will store all N words. Therefore, the auxiliary space used grows linearly with the number of words in the input list, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
words is null or empty	Return an empty list since there are no words to search.
char is null or empty string	Return an empty list because no characters are provided to search for.
words contains empty strings	An empty string cannot contain a character, so skip it.
words contains null strings	Treat null strings as empty strings and skip them.
words contains very long strings	The linear scan through each word should still work, but consider potential performance implications for extremely long words.
char appears at the beginning of a word.	The character search should correctly identify words that start with the target character.
char appears at the end of a word.	The character search should correctly identify words that end with the target character.
words contains duplicate strings	The algorithm will correctly identify the index of each occurrence of the duplicate strings if they contain the character; duplicates do not affect correctness.

words is null or empty

How to Handle:

Return an empty list since there are no words to search.

char is null or empty string

How to Handle:

Return an empty list because no characters are provided to search for.

words contains empty strings

How to Handle:

An empty string cannot contain a character, so skip it.

words contains null strings

How to Handle:

Treat null strings as empty strings and skip them.

words contains very long strings

How to Handle:

The linear scan through each word should still work, but consider potential performance implications for extremely long words.

char appears at the beginning of a word.

How to Handle:

The character search should correctly identify words that start with the target character.

char appears at the end of a word.

How to Handle:

The character search should correctly identify words that end with the target character.

words contains duplicate strings

How to Handle:

The algorithm will correctly identify the index of each occurrence of the duplicate strings if they contain the character; duplicates do not affect correctness.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input `words` array contain null or empty strings?
Is the `character` a single character, or could it be a string of multiple characters?
Is the `character` case-sensitive? Should I consider case-insensitive matching?
What should be returned if none of the words contain the specified character? An empty array?
Are there any limitations on the length of individual words within the `words` array?

Brute Force Solution

Approach

The brute-force approach involves going through each word in the provided list. For every word, we simply check if the target character is present within that word.

Here's how the algorithm would work step-by-step:

Take the first word from the list.
Look at each letter in the word to see if any of them match the character we're searching for.
If we find a match, remember the position of that word in the original list.
Move on to the next word in the list and repeat the process of checking each letter.
Keep repeating this process until we have checked every single word in the list.
Finally, provide a list of all the positions where we found words containing the specified character.

Code Implementation

def find_words_containing_character(words, character):
    indices_of_matching_words = []

    for word_index in range(len(words)):
        word = words[word_index]

        # Iterate through each character to find match
        for char_index in range(len(word)):
            if word[char_index] == character:

                # Store index because the word contains char
                indices_of_matching_words.append(word_index)

                break

    # Return all of the word indices that match
    return indices_of_matching_words

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first word from the list.
Check if the specific character is present anywhere in that word.
If the character is present, save that word to a separate list of 'found' words.
Repeat this process for every word in the original list.
Once you've checked all the words, the separate list contains all the words that include the specific character.

Code Implementation

def find_words_containing_character(words, character):
    words_containing_char = []

    # Iterate through each word in the input list
    for word in words:
        # Check if the character is present in the current word
        if character in word:

            # Add the word to result if the character is found
            words_containing_char.append(word)

    return words_containing_char

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
words is null or empty	Return an empty list since there are no words to search.
char is null or empty string	Return an empty list because no characters are provided to search for.
words contains empty strings	An empty string cannot contain a character, so skip it.
words contains null strings	Treat null strings as empty strings and skip them.
words contains very long strings	The linear scan through each word should still work, but consider potential performance implications for extremely long words.
char appears at the beginning of a word.	The character search should correctly identify words that start with the target character.
char appears at the end of a word.	The character search should correctly identify words that end with the target character.
words contains duplicate strings	The algorithm will correctly identify the index of each occurrence of the duplicate strings if they contain the character; duplicates do not affect correctness.

words is null or empty

How to Handle:

Return an empty list since there are no words to search.

char is null or empty string

How to Handle:

Return an empty list because no characters are provided to search for.

words contains empty strings

How to Handle:

An empty string cannot contain a character, so skip it.

words contains null strings

How to Handle:

Treat null strings as empty strings and skip them.

words contains very long strings

How to Handle:

The linear scan through each word should still work, but consider potential performance implications for extremely long words.

char appears at the beginning of a word.

How to Handle:

The character search should correctly identify words that start with the target character.

char appears at the end of a word.

How to Handle:

The character search should correctly identify words that end with the target character.

words contains duplicate strings

How to Handle:

The algorithm will correctly identify the index of each occurrence of the duplicate strings if they contain the character; duplicates do not affect correctness.