2942. Find Words Containing Character
Problem Description
You are given an array of strings, where each string is indexed starting from 0 - this is what is meant by a "0-indexed" array. Your task is to find and return the indices of all strings in this array that contain a specific character x
. The character x
is provided to you, and you need to search through each string in the array to check if x
is included in that string. If it is, you keep track of that string's index. Once you're done checking all the strings, you produce an array of these indices. It's important to note that the order of these indices in the final array does not matter.
Intuition
The intuition behind the solution is pretty straightforward. Since we only need to know whether a character exists in the words, we can simply iterate through each word in the list and check for the presence of the character x
. This can be done easily with the help of Python's in
keyword, which checks for the presence of a substring in a string.
For efficiency, we use a list comprehension which allows us to iterate through the list of words and at the same time, keep track of the index of each word. We leverage enumerate()
here, which returns both the index and the corresponding word. The condition if x in w
inside the list comprehension checks if the character x
is in the current word w
. If it is, the index i
gets added to the output list. This process continues for each word in the list words
.
By the end of the iteration, the list comprehension will have generated a list containing the indices of all the words that contain the character x
, satisfying the problem requirement.
Solution Approach
For the given problem, the solution uses a simple yet effective approach that does not require complex algorithms or data structures. The approach follows a sequential procedure using basic operations provided by Python:
-
Iteration with Enumeration:
- Python's built-in
enumerate()
function is used, which is a common pattern when you need to traverse a list and also keep track of indices. enumerate(words)
gives us a neat way to loop overwords
while having access to both the indexi
and wordw
at the same time.
- Python's built-in
-
Membership Testing:
- Inside the loop, we use the membership operator
in
which checks whether the characterx
is present in the wordw
. This operation is performed for every word in the list. - The condition
x in w
evaluates to eitherTrue
ifx
is found inside the stringw
, orFalse
otherwise.
- Inside the loop, we use the membership operator
-
List Comprehension:
- A list comprehension is utilized to build the resulting list of indices in a clean and efficient one-liner.
- This eliminates the need for initializing an empty list beforehand and appending indices one by one inside a for-loop.
-
Conditional Expression in List Comprehension:
- The list comprehension has a form of
[expression for item in iterable if condition]
, where theexpression
is simply the indexi
. - The condition in our case is
if x in w
, and it ensures that the indexi
is included in the final list only if the wordw
contains the characterx
.
- The list comprehension has a form of
The function findWordsContaining
returns the list that is generated by the list comprehension, which includes all indices i
where the condition x in w
holds true.
In summary, the solution achieves the goal by using iteration to go through each word, using the membership test to find words containing the character x
, and a list comprehension to build the list of indices efficiently. This is a direct and practical approach that leverages Python's language features to solve the problem succinctly.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach described above.
Imagine we are given an array of strings words = ["apple", "banana", "cherry", "date"]
and the character x = 'a'
. We want to find all the indices of strings containing the character 'a'
.
Following the solution approach:
-
Iteration with Enumeration: We start by enumerating the list
["apple", "banana", "cherry", "date"]
. This means we get pairs of indices and words like(0, "apple")
,(1, "banana")
,(2, "cherry")
, and(3, "date")
. -
Membership Testing:
- For
(0, "apple")
, we check if'a'
is in"apple"
. It is, so this index (0) could be part of our resulting list. - Then for
(1, "banana")
,'a'
is also found in"banana"
. Index (1) should also be part of our resulting list. - For
(2, "cherry")
,'a'
is not found, so we skip this index. - Finally, for
(3, "date")
,'a'
is again not found, so we also skip this index.
- For
-
List Comprehension: Using list comprehension, we combine the steps of enumeration and membership testing into one line. It would look like this:
[i for i, w in enumerate(words) if x in w]
Executing this line with our example list would produce
[0, 1]
since those are the indices of the words containing the letter'a'
. -
Conditional Expression in List Comprehension: The conditional (
if x in w
) ensures that only indices of words containing'a'
are included in the final list.
Putting it all together, the function findWordsContaining(['apple', 'banana', 'cherry', 'date'], 'a')
returns the list [0, 1]
, successfully identifying the indices of words that contain the character 'a'
.
Solution Implementation
1class Solution:
2 def find_words_containing(self, words: List[str], char_sequence: str) -> List[int]:
3 """
4 Find and return the indices of words that contain the specified character sequence.
5
6 Parameters:
7 words: List of strings to search within.
8 char_sequence: String sequence to find in the words list.
9
10 Returns:
11 List of indices of words that contain the char_sequence.
12 """
13
14 # Use list comprehension to find indices of words containing the specified character sequence
15 indices = [index for index, word in enumerate(words) if char_sequence in word]
16
17 return indices
18
1import java.util.List;
2import java.util.ArrayList;
3
4class Solution {
5
6 // This method finds and returns the indices of the words containing a specific character.
7 public List<Integer> findWordsContaining(String[] words, char targetChar) {
8 // List to store indices of words containing the target character.
9 List<Integer> indicesWithTargetChar = new ArrayList<>();
10
11 // Iterate over the array of words.
12 for (int index = 0; index < words.length; ++index) {
13 // Check if the current word contains the target character.
14 if (words[index].indexOf(targetChar) != -1) {
15 // If it does, add the index of this word to the list.
16 indicesWithTargetChar.add(index);
17 }
18 }
19 // Return the list of indices.
20 return indicesWithTargetChar;
21 }
22}
23
1#include <vector>
2#include <string>
3
4class Solution {
5public:
6 // Function to find and return the indices of words containing a specific character 'x'
7 std::vector<int> findWordsContaining(std::vector<std::string>& words, char x) {
8 std::vector<int> indices; // Vector to store indices of words containing the character 'x'
9
10 // Iterate through all the words in the vector
11 for (int i = 0; i < words.size(); ++i) {
12 // Check if the current word contains the character 'x'
13 if (words[i].find(x) != std::string::npos) {
14 indices.push_back(i); // If 'x' is found, add the index to the results vector
15 }
16 }
17
18 return indices; // Return the vector of indices
19 }
20};
21
1// This function finds the indices of all words containing a specified substring.
2// words: Array of strings to be searched.
3// query: Substring to search for within the array elements.
4// Returns an array of indices where the substring is found.
5function findWordsContaining(words: string[], query: string): number[] {
6 // Initialize an empty array to store the indices.
7 const indicesOfWordsContainingQuery: number[] = [];
8
9 // Loop through each word in the 'words' array.
10 for (let index = 0; index < words.length; ++index) {
11 // Check if the current word contains the substring 'query'.
12 if (words[index].includes(query)) {
13 // If so, add the index of this word to our result array.
14 indicesOfWordsContainingQuery.push(index);
15 }
16 }
17
18 // Return the array of indices where the substring is found.
19 return indicesOfWordsContainingQuery;
20}
21
Time and Space Complexity
The time complexity of the given code snippet can be understood by considering each operation in the list comprehension. The function iterates through each word in the list words
and checks if the substring x
is present in each word w
. This operation involves checking each character in each word against the characters in x
until a match is found or the word is exhausted. Thus, if we let L
be the sum of the lengths of all the strings in the list words
, the worst-case scenario is when x
is not present in any word, resulting in a time complexity of O(L)
.
The space complexity of the function, aside from the output list, is O(1)
. This is because the only extra space used is for the loop iteration variable and the index i
, which do not depend on the input size. Therefore, the space used for the function's operations other than the storage for the return list is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!