数组中的字符串匹配

[yankewei]

给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。

如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ，那么字符串 words[i] 就是 words[j] 的一个子字符串。

示例 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 <= words.length <= 100
• 1 <= words[i].length <= 30
• words[i] 仅包含小写英文字母。
• 题目数据 保证 每个 words[i] 都是独一无二的。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/string-matching-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[yankewei]

这个题第一直觉可以用模拟来做，如果一个字符串 a 是 另一个字符串 b 的子字符串，那么 a 的长度肯定小于 b，并且题目要求返回值不需要有顺序，所以可以先根据字符串的长度对数组进行排序，方便我们去遍历.

class Solution {

    /**
     * @param String[] $words
     * @return String[]
     */
    function stringMatching($words) {
        $result = [];
        usort($words, fn($a, $b) => strlen($a) > strlen($b) ? 1 : -1);

        for ($i = 0; $i < count($words); $i++) {
            for ($j = $i+1; $j < count($words); $j++) {
                if (strstr($words[$j], $words[$i]) !== false) {
                    $result[] = $words[$i];
                    break;
                }
            }
        }

        return $result;
    }
}

另一种解法把数组元素拼接成一个长字符串 str ，然后再去查找，如果一个元素在 str 中出现至少两次（一次是自己，一次是在另一个字符串的子字符串），比如["et","code","leetcode"]，拼接之后的字符串是etcodeleetcode，et出现了两次，一个是自己，另一次是做为leetcode的子字符串。但是这个解法有两个需要注意的点:

• 字符串拼接时需要一个非英文字母字符，不能使用空字符串，例如 ["abc","de","abcd"]，abcd出现了两次，但其实它不是我们需要的。
• 需要对字符串进行切割，匹配第一次后，找到位置的 point，然后加上字符串的长度。

class Solution {

    /**
     * @param String[] $words
     * @return String[]
     */
    function stringMatching($words) {
        $result = [];
        $str = implode('+', $words);

        foreach ($words as $word) {
            if (strpos(substr($str, strpos($str, $word) + strlen($word)), $word) !== false) {
                $result[] = $word;
            }
        }

        return $result;
    }
}

func stringMatching(words []string) []string {
    str := strings.Join(words, "+")
    result := []string{}

    for _, word := range words {
        if (strings.Index(string(str[strings.Index(str, word) + len(word):]), word) != -1) {
            result = append(result, word)
        }
    }

    return result
}