1408. String Matching in an Array

Time: O(n² · m)

Space: O(n)

Intuition

A string is a string matching of another if it appears as a substring. Use string matching or sort by length; shorter strings are substrings of longer ones.

Algorithm

1For each string s: check if any other string t (s != t) contains s as a substring.
2Use contains() or KMP for each pair.

Common Pitfalls

•O(n^2 * L) is acceptable. Sort by length descending; longest strings cannot be substrings of shorter ones.

1408.cs

// Approach: Brute-force; for each word check if it appears as a substring of any longer word.
// Time: O(n² · m) Space: O(n)

public class Solution
{
    public IList<string> StringMatching(string[] words)
    {
        List<string> ans = new List<string>();
        foreach (var a in words)
        {
            foreach (var b in words)
            {
                if (a.Length < b.Length && b.IndexOf(a) != -1)
                {
                    ans.Add(a);
                    break;
                }
            }
        }
        return ans;
    }
}

Was this solution helpful?