LeetCode个人题解

LeetCode | 1408. String Matching

2020-04-12  本文已影响0人  Wonz

LeetCode 1408. String Matching in an Array数组中的字符串匹配【Easy】【Python】【字符串】

Problem

LeetCode

Given an array of string words. Return all strings in words which is substring of another word in any order.

String words[i] is substring of words[j], if can be obtained removing some characters to left and/or right side of words[j].

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: []

Constraints:

问题

力扣

给你一个字符串数组 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"]
输出:[]

提示:

思路

字符串

暴力,最后要去重。

时间复杂度: O(n^2)
空间复杂度: O(n)

Python3代码
from typing import List
import copy

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        n = len(words)
        res = []
        for i in range(n):
            temp = copy.deepcopy(words)
            temp.remove(words[i])

            for j in range(n - 1):
                if words[i] in temp[j]:
                    res.append(words[i])
        return list(set(res))

GitHub链接

Python

上一篇 下一篇

猜你喜欢

热点阅读