1524. String Matching In An Array¶

LeetCode Problem View on GitHub

1524. String Matching in an Array

Easy

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

A substring is a contiguous sequence of characters within a string

Example 1:

Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
Explanation: "as" is substring of "mass" and "hero" is substring of "superhero".
["hero","as"] is also a valid answer.

Example 2:

Input: words = ["leetcode","et","code"]
Output: ["et","code"]
Explanation: "et", "code" are substring of "leetcode".

Example 3:

Input: words = ["blue","green","bu"]
Output: []
Explanation: No string of words is substring of another string.

Constraints:

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

Solution¶

class Solution {
    public List<String> stringMatching(String[] words) {
        int n = words.length;
        List<String> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (check(words[j], words[i])) {
                    res.add(words[i]);
                    break;
                }
            }
        }
        return res;
    }
    private boolean check(String s, String t) {
        int n = s.length(), m = t.length();
        if (m > n) return false;
        for (int i = 0; i < n; i++) {
            if (i + m - 1 >= n) break;
            String current = s.substring(i, i + m);
            if (current.equals(t)) return true;
        }
        return false;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here