Leetcode 1408. String Matching in an Array

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

String Matching in an Array

2. Solution

• Version 1

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        result = set()
        length = len(words)
        flags = [0 for i in range(length)]
        for i in range(length):
            if flags[i]:
                continue
            for j in range(i+1, length):
                if flags[j]:
                    continue
                if len(words[i]) < len(words[j]):
                    if words[i] in words[j]:
                        flags[i] = 1
                        result.add(words[i])
                else:
                    if words[j] in words[i]:
                        flags[j] = 1
                        result.add(words[j])
        return result

• Version 2

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        words.sort(key=len) 
        result = set()
        length = len(words)
        for i in range(length):
            for j in range(i+1, length):
                if words[i] in words[j]:
                    result.add(words[i])
                    break
        return result

Reference

1. https://leetcode.com/problems/string-matching-in-an-array/