algoadvance

Leetcode 1408. String Matching in an Array

Problem Statement

Given an array of string words, return all strings in words that are a substring of another word in any order. A string words[i] is a substring of words[j], if i != j and words[i] is a substring of words[j].

Example:

Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]

Input: words = ["leetcode","et","code"]
Output: ["et","code"]

Clarifying Questions

  1. Case Sensitivity: Are the words case-sensitive?
    • Yes, treat the strings as case-sensitive.
  2. Input Constraints: Are there any constraints on the length of the array or the length of individual strings?
    • The length of words and individual strings should be reasonable to fit into memory.
  3. Output Order: Is there any specific order in which we need to return the substrings?
    • No, the output order does not matter.
  4. Duplicates: Can words contain duplicate strings?
    • Yes, words can contain duplicates.

Strategy

  1. Brute Force Approach:
    • Loop through each combination of two words from the array.
    • For each pair, check if one string is a substring of the other.
    • If it is, add the substring to the result set.
    • Using a set will help to maintain unique substrings.
  2. Steps:
    1. Initialize an empty set substrings to store unique substrings.
    2. Loop through each word in the list.
    3. Inside this loop, run another loop to check every other word to see if the current word is a substring of the other.
    4. If the current word is a substring of another word, add it to the set.
    5. Convert the set to a list and return it.

Code

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

public class StringMatchingInAnArray {
    public List<String> stringMatching(String[] words) {
        // Initialize a HashSet to keep track of unique substrings
        HashSet<String> substrings = new HashSet<>();
        
        // Length of the words array
        int n = words.length;
        
        // Loop through each pair of words in the array
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && words[j].contains(words[i])) {
                    substrings.add(words[i]);
                }
            }
        }
        
        // Convert the set to a list and return it
        return new ArrayList<>(substrings);
    }
    
    public static void main(String[] args) {
        StringMatchingInAnArray solution = new StringMatchingInAnArray();
        String[] words1 = {"mass","as","hero","superhero"};
        System.out.println(solution.stringMatching(words1)); // Output: [as, hero]
        
        String[] words2 = {"leetcode","et","code"};
        System.out.println(solution.stringMatching(words2)); // Output: [et, code]
    }
}

Time Complexity

  1. Time Complexity:
    • The worst-case time complexity is (O(n^2 \cdot m));
      • (n): Number of words in the array.
      • (m): Average length of a word.
    • Each word is checked against every other word to see if it is a substring, leading to (O(n^2)) comparisons, and the contains() method runs in (O(m)).
  2. Space Complexity:
    • The space complexity is (O(n)) to store up to n substrings in the HashSet and the final list.

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