String Matching in an Array

Leetcode Problem:

• String Matching in an Array

Summary

• Given an array of strings, return all strings that are a substring of another word.

Approach

• The solution iterates over each word in the input array and checks if it is a substring of any other word in the array
• It uses nested loops to compare characters between words.

Complexity

• O(n^3) where n is the number of words in the input array

Explanation

• The solution iterates over each word in the input array and checks if it is a substring of any other word in the array
• It uses nested loops to compare characters between words
• The outer loop iterates over each word, the middle loop checks if the current word is a substring of any other word, and the inner loop compares characters between words
• If a word is found to be a substring of another word, it is added to the result array and the middle loop is terminated to avoid unnecessary comparisons.

Solution Code:

class Solution {
public:
    vector stringMatching(vector& words) {
        vector ans;
        for(int i = 0 ; i < words.size(); i++){
            bool success = false;
            for(int j = 0; j < words.size(); j++){
                if(i == j) continue;
                for(int k = 0; k < words[j].size(); k++){
                    int l = 0;
                    for(; l < words[i].size(); l++){
                        if(words[j][k+l] != words[i][l]) break;
                    }
                    if(l == words[i].size()){
                        ans.push_back(words[i]);
                        success = true;
                        break;
                    }
                }
                if(success) break;
            }
        }
        return ans;
    }
};