Problem

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.

Examples

Example 1:

1
2
3

Input: words = ["leet","code"], x = "e"
Output: [0,1]
Explanation: "e" occurs in both words: "l** _ee_** t", and "cod _**e**_ ". Hence, we return indices 0 and 1.

Example 2:

1
2
3

Input: words = ["abc","bcd","aaaa","cbc"], x = "a"
Output: [0,2]
Explanation: "a" occurs in "**_a_** bc", and "_**aaaa**_ ". Hence, we return indices 0 and 2.

Example 3:

1
2
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.

Solution

Method 1 - Iteration

To solve this problem:

  1. Iterate through the words array while keeping track of the index.
  2. For each word, check if the character x exists in the word (using contains in Java or the in operator in Python).
  3. If x exists in the word, append the index to the resulting array.
  4. Return the resulting array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public class Solution {
    public List<Integer> findWordsContainingChar(String[] words, char x) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            if (words[i].indexOf(x) != -1) {
                ans.add(i);
            }
        }
        return ans;
    }
1
2
3
4
5
6
7

class Solution:
    def findWordsContainingChar(self, words: List[str], x: str) -> List[int]:
        ans: List[int] = []
        for idx, word in enumerate(words):
            if x in word:
                ans.append(idx)
        return ans

Complexity

  • ⏰ Time complexity: O(n*m)
    • Checking for x in a word: Assuming m as the average length of words, the check takes O(m) time.
    • Iteration through the array: If the array has n elements, the total iteration takes O(n).
    • Overall: The time complexity is O(n * m).
  • 🧺 Space complexity: O(n)
    • Elements in the ans array are indices. Its space complexity is proportional to the size of the output (up to O(n)).
    • No additional space apart from the result array is used, so the space complexity is O(n).