LeetCode | 1408. String Matching in an Array配列の文字列一致【Python】


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:
  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 30
  • words[i] contains only lowercase English letters.
  • It’s guaranteed that words[i] will be unique.

  • に質問
    スナップ
    文字列配列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]ごとにユニークであることを保証する.

  • 構想
    文字列
      ,     。
    

    時間複雑度:O(n^2)空間複雑度:O(n)
    Python 3コード
    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