String Matching in an Array

Easy
1180.

String Matching in an Array

String Matching in an Array is an easy coding problem on arrays, strings and string matching, asked in Amazon and Microsoft interviews.

You are given an array words of distinct lowercase strings.

Return every string of words that occurs as a substring (a contiguous run of characters) of some other string of words. List them in the order they appear in words; return an empty list if there are none.

Example 1

Input
words = ["kairo","air","code","od","duel"]
Output
["air","od"]
Explanation
`"air"` sits inside `"kairo"` and `"od"` inside `"code"`.

Example 2

Input
words = ["bug","hunt","bughunt"]
Output
["bug","hunt"]

Example 3

Input
words = ["abc","xyz"]
Output
[]

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 30
  • words[i] contains only lowercase English letters
  • all the strings of words are unique
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @return {string[]}
 */
var stringMatching = function(words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

String Matching in an Array — Solution in Python, Java & C++

String Matching in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

String Matching in an Array is an easy coding problem on arrays, strings and string matching, asked in Amazon and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Arrays, Strings, String Matching
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array words of distinct lowercase strings.

Return every string of words that occurs as a substring (a contiguous run of characters) of some other string of words. List them in the order they appear in words; return an empty list if there are none.

Example 1

Input: words = ["kairo","air","code","od","duel"]
Output: ["air","od"]
Explanation: `"air"` sits inside `"kairo"` and `"od"` inside `"code"`.

Example 2

Input: words = ["bug","hunt","bughunt"]
Output: ["bug","hunt"]

Example 3

Input: words = ["abc","xyz"]
Output: []

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 30
  • words[i] contains only lowercase English letters
  • all the strings of words are unique

Hints for String Matching in an Array

  1. Hint 1

    With at most 100 short words, comparing every pair is cheap.

  2. Hint 2

    For each word, look for another word (a different index) that contains it.

  3. Hint 3

    Stop searching for a word as soon as one container is found, so it is reported only once.

How to solve String Matching in an Array

The limits are tiny, so test every ordered pair (i, j) with i != j and ask whether words[j] contains words[i] using the language's substring search.

Approach

  1. For each index i in order:
  2. Scan every j != i; if words[i] is a substring of words[j], append words[i] to the answer and stop scanning for this i.
  3. Return the answer.

Why it works

A word belongs to the answer exactly when some other word contains it, which is what the inner scan checks. Breaking after the first container keeps each word at most once, and the outer loop runs in input order.

Complexity

  • Time — O(n² · L²) worst case with naive substring search (L ≤ 30)
  • Space — O(1) besides the output

Pitfalls

  • Skip j == i: every word contains itself.
  • Report a word once even if several words contain it.
  • Only a longer (or equal-length, impossible here since words are distinct) word can contain another — an optional speed-up, not a requirement.

Reference solution

Python

from typing import List

def stringMatching(words: List[str]) -> List[str]:
    res = []
    for i, w in enumerate(words):
        if any(i != j and w in x for j, x in enumerate(words)):
            res.append(w)
    return res

Java

public static 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.toArray(new String[0]);
}

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings