1408. String Matching in an Array
Problem
Given an array of string words, return all strings in words that is a substring of another word. You can return the answer in any order.
A substring is a contiguous sequence of characters within a string.
https://leetcode.com/problems/string-matching-in-an-array/
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:[]
Explanation: No string of words is substring of another string.
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 30words[i]contains only lowercase English letters.- All the strings of
wordsare unique.
Test Cases
class Solution:
def stringMatching(self, words: List[str]) -> List[str]:import pytest
from solution import Solution
@pytest.mark.parametrize('words, expected', [
(["mass","as","hero","superhero"], ["as","hero"]),
(["leetcode","et","code"], ["et","code"]),
(["blue","green","bu"], []),
(["leetcoder","leetcode","od","hamlet","am"], ["leetcode","od","am"])
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, words, expected):
assert sorted(sol.stringMatching(words.copy())) == sorted(expected)
Thoughts
先对 words 按单词长度排序,可以减少后续的循环次数,并能很好地避免重复输出。
用两重循环比较任意两个字符串,看较长的是否包含较短的。
时间复杂度 O(n²),额外的空间复杂度 O(1)。
Code
class Solution:
def stringMatching(self, words: list[str]) -> list[str]:
words.sort(key=lambda w: len(w))
res = []
n = len(words)
for i in range(n - 1):
a = words[i]
for j in range(i + 1, n):
b = words[j]
if a in b:
res.append(a)
break
return res
评论需要 JavaScript。