leetcode 2273. Find Resultant Array After Removing Anagrams（python）

語言: CN / TW / HK
時間 2022-05-20 12:15:21

描述

You are given a 0-indexed string array words, where words[i] consists of lowercase English letters.

In one operation, select any index i such that 0 < i < words.length and words[i - 1] and words[i] are anagrams, and delete words[i] from words. Keep performing this operation as long as you can select an index that satisfies the conditions.

Return words after performing all operations. It can be shown that selecting the indices for each operation in any arbitrary order will lead to the same result.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase using all the original letters exactly once. For example, "dacb" is an anagram of "abdc".

Example 1:

Input: words = ["abba","baba","bbaa","cd","cd"]
Output: ["abba","cd"]
Explanation:
One of the ways we can obtain the resultant array is by using the following operations:
- Since words[2] = "bbaa" and words[1] = "baba" are anagrams, we choose index 2 and delete words[2].
  Now words = ["abba","baba","cd","cd"].
- Since words[1] = "baba" and words[0] = "abba" are anagrams, we choose index 1 and delete words[1].
  Now words = ["abba","cd","cd"].
- Since words[2] = "cd" and words[1] = "cd" are anagrams, we choose index 2 and delete words[2].
  Now words = ["abba","cd"].
We can no longer perform any operations, so ["abba","cd"] is the final answer.

Example 2:

Input: words = ["a","b","c","d","e"]
Output: ["a","b","c","d","e"]
Explanation:
No two adjacent strings in words are anagrams of each other, so no operations are performed.

Note:

1 <= words.length <= 100
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.

解析

根據題意，給定一個索引為 0 的字串陣列 words，其中 words[i] 由小寫英文字母組成。在一個操作中，選擇任何索引 i 使得 0 < i < words.length 並且 words[i-1] 和 words[i] 是 anagrams ，將 words[i] 從 words 中刪除。 只要可以選擇滿足條件的索引，就一直執行這個操作。anagrams 表示相同的字母集合通過不同順序展現出的不同字串。 例如，“dacb”是“abdc” 的 anagrams。

這道題其實就是考察一個字串的計數器使用方法，我們既然用 python ，肯定要使用 collections.Counter 這個函式，我們只要根據題意介紹的 anagrams 定義，開始在 result 中放入第一個字串，然後從第二個字串開始找，只要新來的字串 a 和 result 最後一個字串 b 兩個字串的計數器 a 和 b 不同的情況下，才會將新的字串加入到結果中，遍歷結束之後。

時間複雜度為 O(N) ，空間複雜度為 O(N)。

解答

class Solution(object):
    def removeAnagrams(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        result = [words[0]]
        for i in range(1, len(words)):
            a = collections.Counter(words[i])
            b = collections.Counter(result[-1])
            if a!=b:
                result.append(words[i])
        return result

執行結果

201 / 201 test cases passed.
Status: Accepted
Runtime: 103 ms
Memory Usage: 13.6 MB

原題連結

http://leetcode.com/contest/weekly-contest-293/problems/find-resultant-array-after-removing-anagrams/

您的支援是我最大的動力

「」
「」