DEV Community

Cover image for 1408. String Matching in an Array
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

3 1 1

1408. String Matching in an Array

1408. String Matching in an Array

Difficulty: Easy

Topics: Array, String, String Matching

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.

Hint:

  1. Bruteforce to find if one string is substring of another or use KMP algorithm.

Solution:

We need to find all strings in the words array that are substrings of another word in the array, you can use a brute force approach. The approach involves checking each string in the list and verifying if it's a substring of any other string.

Let's implement this solution in PHP: 1408. String Matching in an Array

<?php
/**
 * @param String[] $words
 * @return String[]
 */
function stringMatching($words) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$words = ["mass", "as", "hero", "superhero"];
print_r(stringMatching($words));

// Example 2
$words = ["leetcode", "et", "code"];
print_r(stringMatching($words));

// Example 3
$words = ["blue", "green", "bu"];
print_r(stringMatching($words));
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  1. The function stringMatching loops through all the words in the input array.
  2. For each word, it compares it with every other word in the array using a nested loop.
  3. It uses PHP's strpos() function to check if one string is a substring of another. The strpos() function returns false if the substring is not found.
  4. If a substring is found, we add the word to the result array and break out of the inner loop, as we only need to record the word once.
  5. Finally, the function returns the result array containing all the substrings.

Time Complexity:

  • The time complexity is O(n2 x m), where n is the number of words and m is the maximum length of a word. This is because we are performing a substring search for each word within every other word.

Example Outputs:

For input ["mass", "as", "hero", "superhero"], the output will be:

Array
(
    [0] => as
    [1] => hero
)
Enter fullscreen mode Exit fullscreen mode

For input ["leetcode", "et", "code"], the output will be:

Array
(
    [0] => et
    [1] => code
)
Enter fullscreen mode Exit fullscreen mode

For input ["blue", "green", "bu"], the output will be:

Array
(
)
Enter fullscreen mode Exit fullscreen mode

This solution works well for the given problem constraints.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Billboard image

The fastest way to detect downtimes

Join Vercel, CrowdStrike, and thousands of other teams that trust Checkly to streamline monitoring.

Get started now

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay