Leetcode 1408. String Matching in an Array

Tyan

发布于 2021-07-01 10:30:07

2700

发布于 2021-07-01 10:30:07

文章被收录于专栏：SnailTyan

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

1. Description

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