DDSA Solutions

1408. String Matching in an Array

UnknownView on LeetCode
ArrayStringString Matching
Time: O(n² · m)
Space: O(n)

Problem Overview

A string is a string matching of another if it appears as a substring.

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

  1. 1For each string s: check if any other string t (s != t) contains s as a substring.
  2. 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
C#
// 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?

Related Problems