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));
?>




<h3>
  
  
  Explanation:
</h3>

<ol>
<li>The function stringMatching loops through all the words in the input array.</li>
<li>For each word, it compares it with every other word in the array using a nested loop.</li>
<li>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.</li>
<li>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.</li>
<li>Finally, the function returns the result array containing all the substrings.</li>
</ol>

<h3>
  
  
  Time Complexity:
</h3>

<ul>
<li>The time complexity is <em><strong>O(n<sup>2</sup> x m)</strong></em>, where <em><strong>n</strong></em> is the number of words and <em><strong>m</strong></em> is the maximum length of a word. This is because we are performing a substring search for each word within every other word.</li>
</ul>

<h3>
  
  
  Example Outputs:
</h3>

<p>For input ["mass", "as", "hero", "superhero"], the output will be:<br>
</p>

<pre class="brush:php;toolbar:false">Array
(
    [0] => as
    [1] => hero
)

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

Array
(
    [0] => et
    [1] => code
)

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

Array
(
)

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:

• LinkedIn
• GitHub

The above is the detailed content of String Matching in an Array. For more information, please follow other related articles on the PHP Chinese website!