数组中的字符串匹配

1408。数组中的字符串匹配

难度：简单

主题：数组、字符串、字符串匹配

给定一个字符串单词数组，返回单词中作为另一个单词的子字符串的所有字符串。您可以按任何顺序返回答案。

子字符串是字符串中连续的字符序列

示例1：

• 输入：words = ["mass","as","hero","superhero"]
• 输出： ["as","hero"]
• 解释：“as”是“mass”的子字符串，“hero”是“superhero”的子字符串。 ["hero","as"] 也是一个有效的答案。

示例2：

• 输入：words = ["leetcode","et","code"]
• 输出： ["et","code"]
• 解释：“et”、“code”是“leetcode”的子字符串。

示例 3：

• 输入：words = ["blue","green","bu"]
• 输出： []
• 解释：没有任何字符串是另一个字符串的子串。

约束：

• 1
• 1
• words[i] 仅包含小写英文字母。
• 所有字符串都是唯一。

提示：

1. 暴力破解一个字符串是否是另一个字符串的子字符串或使用 KMP 算法。

解决方案：

我们需要找到words数组中作为数组中另一个单词的子串的所有字符串，您可以使用暴力方法。该方法涉及检查列表中的每个字符串并验证它是否是任何其他字符串的子字符串。

让我们用 PHP 实现这个解决方案：1408。数组中的字符串匹配

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

解释：

1. 函数 stringMatching 循环遍历输入数组中的所有单词。
2. 对于每个单词，它使用嵌套循环将其与数组中的每个其他单词进行比较。
3. 它使用 PHP 的 strpos() 函数来检查一个字符串是否是另一个字符串的子字符串。如果未找到子字符串，strpos() 函数将返回 false。
4. 如果找到子字符串，我们会将单词添加到结果数组中并跳出内循环，因为我们只需要记录该单词一次。
5. 最后，函数返回包含所有子字符串的结果数组。

时间复杂度：

• 时间复杂度为 O(n² x m)，其中 n 是单词，m 是单词的最大长度 单词。这是因为我们正在对每个其他单词中的每个单词执行子字符串搜索。

示例输出：

对于输入 ["mass", "as", "hero", "superhero"]，输出将为：

Array
(
    [0] => as
    [1] => hero
)

对于输入 ["leetcode", "et", "code"]，输出将是：

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

对于输入 ["blue", "green", "bu"]，输出将是：

Array
(
)

该解决方案对于给定的问题约束非常有效。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是数组中的字符串匹配的详细内容。更多信息请关注PHP中文网其他相关文章！