algoadvance

Leetcode 2942. Find Words Containing Character

Problem Statement

You are asked to find all the words in a given list that contain a specific character.

Clarifying Questions

1. Input Format:
   • What is the format of the input?
     • You will be given a list of words (strings) and a single character.
2. Character Case Sensitivity:
   • Should the character search be case-sensitive?
     • Typically, searches should be case-sensitive unless specified otherwise. For this problem, we’ll assume case-sensitive search unless told otherwise.
3. Output Format:
   • What is the format of the output?
     • A list containing all strings from the input list that contain the specified character.

Strategy

1. Iterate through the list of words:
   • Check if the specific character is in each word.
2. Filter Words:
   • Collect words that contain the specific character.
3. Return Results:
   • Return the list of filtered words.

Code

import java.util.ArrayList;
import java.util.List;

public class FindWordsContainingCharacter {
    public static List<String> findWordsContainingChar(List<String> words, char ch) {
        List<String> result = new ArrayList<>();
        for (String word : words) {
            if (word.indexOf(ch) >= 0) {
                result.add(word);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // Test cases
        List<String> words = List.of("hello", "world", "leetcode", "java", "python");
        char ch = 'o';

        List<String> result = findWordsContainingChar(words, ch);
        System.out.println(result); // Output: [hello, world]
    }
}

Time Complexity

• Time Complexity:
  • The time complexity of checking if a character exists in a word is O(n) where n is the length of the word.
  • Let m be the number of words in the list and k be the average length of the words. Then checking all words would take O(m * k) time.
• Space Complexity:
  • The space complexity is O(m) for storing the results, assuming the filtered words roughly retain the same space as the input list.

This solution appropriately handles the given problem by iterating through the list of words and checking for the presence of the character in each word.

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?