LeetCode --- 字符串系列 --- 数组中的字符串匹配

数组中的字符串匹配

题目

给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。

请你按任意顺序返回 words 中是其他单词的子字符串的所有单词。

如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i]

那么字符串 words[i] 就是 words[j] 的一个子字符串。

提示：

1 <= words.length <= 100

1 <= words[i].length <= 30

words[i] 仅包含小写英文字母。

题目数据保证每个 words[i] 都是独一无二的。

示例

示例 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"]
输出：[]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/string-matching-in-an-array

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

1、双重循环对比，判断 `各自` 是否是 `其他元素` 的 `子元素`

2、只有 `较短字符串` 才能是 `较长字符` 的 `子字符串`

力扣较好题解

1、使用 `空格` 拼接该 `字符串数组` 成为一个 `总字符串`

2、循环数组，将循环到的 `字符串` 构造成一个 `全局匹配的正则`

3、若在拼接后的 `总字符串` 中能够找到 `两个及以上` 的结果
   说明这个 `字符串` 是 `除自己以外某个字符串` 的 `子字符串`

题解

渐进题解 1

// 用时一般，内存消耗一般
执行用时: 72 ms
内存消耗: 35 MB

let stringMatching = function(words) {
    let res = []
    // 双重循环对比，各自是否是其他元素的子元素
    words.forEach((w, index) => {
        // 内循环数组取值：从外循环的序号 + 1 开始截取 words
        // 因为前面的元素已经都经过对比，不需要重复对比了
        words.slice(index + 1).forEach(ow => {
            // 只有 较短字符串 才能是 较长字符 的 子字符串
            if (w.length > ow.length) {
                if (w.indexOf(ow) > -1) {
                    res.push(ow)
                }
            } else {
                if (ow.indexOf(w) > -1) {
                    res.push(w)
                }
            }
        })
    })
    // 最后 Set 去重
    return [...new Set(res)]
}

渐进题解 2

// 用时一般，内存消耗一般
执行用时: 72 ms
内存消耗: 34.6 MB

let stringMatching = function(words) {
    // filter 写法
    return words.filter(w => {
        return words.some(ow => ow.indexOf(w) > -1 && w !== ow) 
    })
}

渐进题解 3

// 用时较好，内存消耗一般
执行用时: 64 ms
内存消耗: 34.7 MB

let stringMatching = function(words) {
    let res = []
    // 双重循环对比，各自是否是其他元素的子元素
    words.forEach(w => {
        words.forEach(ow => {
            if (w !== ow && ow.indexOf(w) > -1) {
                res.push(w)
            }
        })
    })
    // 最后 Set 去重
    return [...new Set(res)]
}

力扣较好题解

// 用时一般，内存消耗一般
执行用时: 60 ms
内存消耗: 34.1 MB

let stringMatching = function(words) {
    // 使用 空格 拼接该字符串数组成为一个 总字符串
    let s = words.join(' '),
    r = {},
    res = []
    words.forEach(w => {
        // 循环数组，将循环到的 字符串 构造成一个 全局匹配的正则
        r = new RegExp(w, 'g')
        // 若在拼接后的 总字符串 中能够找到两个及以上的结果
        // 说明这个 字符串 是 除自己以外某个字符串 的子字符串
        if (s.match(r).length > 1) {
            res.push(w)
        }
    })
    return res
}