String Matching in an Array

easy array string string matching

Problem

Given an array of strings words, return all strings in words that are a substring of another word. You may return the answer in any order.

Inputwords = ["mass","as","hero","superhero"]

Output["as","hero"]

"as" appears in "mass"; "hero" appears in "superhero".

words (comma-separated)

def string_matching(words):
    res = []
    for i, w in enumerate(words):
        for j, v in enumerate(words):
            if i != j and w in v:
                res.append(w)
                break
    return res

function stringMatching(words) {
  const res = [];
  for (let i = 0; i < words.length; i++) {
    for (let j = 0; j < words.length; j++) {
      if (i !== j && words[j].includes(words[i])) {
        res.push(words[i]);
        break;
      }
    }
  }
  return res;
}

class Solution {
    public List<String> stringMatching(String[] words) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if (i != j && words[j].contains(words[i])) {
                    res.add(words[i]);
                    break;
                }
            }
        }
        return res;
    }
}

vector<string> stringMatching(vector<string>& words) {
    vector<string> res;
    for (int i = 0; i < (int)words.size(); i++) {
        for (int j = 0; j < (int)words.size(); j++) {
            if (i != j && words[j].find(words[i]) != string::npos) {
                res.push_back(words[i]);
                break;
            }
        }
    }
    return res;
}

Explanation

We want every word that hides inside some other word. The most direct approach is to check each word against all the others and ask: "does this word appear as a substring of that one?"

We loop with two indexes i and j over the same list. For each pair where i != j, we test whether words[i] is contained in words[j] using the built-in substring check (w in v). The i != j guard stops a word from matching itself.

As soon as one container is found for words[i], we add it to the result and break, so the same word is never added twice even if several words contain it.

Example: words = ["mass", "as", "hero", "superhero"]. "as" is inside "mass", and "hero" is inside "superhero", so the answer is ["as", "hero"]. "mass" and "superhero" aren't inside anything, so they're left out.

This compares every pair of words, which is a simple and clear brute-force approach that works well for the small word lists in this problem.

Time: O(n² · L²) Space: O(1)