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 substring is a contiguous sequence of characters within a string.

Clarifying Questions

1. Q: Are the input strings case-sensitive?
   • A: Yes, the strings are case-sensitive.
2. Q: Can a word be a substring of itself?
   • A: No, a word cannot be a substring of itself in the context of the problem.
3. Q: Do we need to consider duplicates in the result?
   • A: No duplicates will be present in the result as each word should appear once no matter how many times it appears as a substring.

Strategy

1. We will iterate over each pair of words in the list.
2. For each pair, check if one word is a substring of the other.
3. If it is, add the substrings to the result set.
4. Convert the set to a vector and return it.

Code

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

using namespace std;

vector<string> stringMatching(vector<string>& words) {
    unordered_set<string> resultSet;
    
    for (size_t i = 0; i < words.size(); i++) {
        for (size_t j = 0; j < words.size(); j++) {
            if (i != j && words[j].find(words[i]) != string::npos) {
                resultSet.insert(words[i]);
                break; // No need to check further if we've found at least one match
            }
        }
    }
    
    return vector<string>(resultSet.begin(), resultSet.end());
}

int main() {
    vector<string> words = {"mass", "as", "hero", "superhero"};
    vector<string> result = stringMatching(words);
    
    for (const string& word : result) {
        cout << word << " ";
    }
    
    return 0;
}

Time Complexity

• Time Complexity: The time complexity is (O(n^2 \cdot m)), where (n) is the size of the words vector and (m) is the average length of words. This complexity arises because we are comparing each pair of words and performing a substring search which, in the worst case, is linear with respect to the length of the word.

• Space Complexity: The space complexity is (O(n)) because we store the results in a set which, in the worst case, could store all words.

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?