iT邦幫忙

1

【小馬的LeetCode練功坊】兩道anagram問題- 49. Group Anagrams 和 438. Find All Anagrams in a String

哈囉,又到了小馬的每日leetcode練功時間了,
今日跟大家分享leetcode上的兩道anagram問題,
anagram是小馬做題目才學到的新單字,
意思是「重組字」,
例如說英文單字ateeat都是由相同的英文字組成,就算是重組字

一、把重組字放在一起

題目: LeetCode- 49. Group Anagrams
題意: 給你一堆字串,把重組字放在同一個陣列中
例子:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

python程式碼,152ms

這一題我沒有想到c++語法怎麼做,
因為python有非常好用的內建函數可以解,
itertools模組內的groupby函數可以把相同性質的元素放在一起,
使用上需要把元素按key事先排序過,
想法上其實很簡單,
本題什麼是「相同性質的元素」呢?

如果是anagram的話,表示將單字按字母順序排列,
結果一定是相同的,
譬如說把英文單字ateeat按字母順序排列一定都是['a', 'e', 't']

程式碼看起來很短很簡單,但值得細細品味,
對python語法需要有一定了解才看的懂

from itertools import groupby

def grouping(arr, KEY_FUNC):
    A = sorted(arr, key = KEY_FUNC)
    return [list(g) for k, g in groupby(A,key=KEY_FUNC)]

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        return grouping(strs, sorted(x))

二、找出字串中所有重組字

題目: LeetCode- 438. Find All Anagrams in a String
題意: 給你一個字串s和非空字串p,請找出所有在s字串中的index,使得以index開頭的子字串是p的重組字
例子:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
index 0開頭的子字串是"cba",是"abc"的重組字。
index 6開頭的子字串是"bac",是"abc"的重組字。

想法: 小馬採用有點暴力的方法,
窮舉s字串裡面長度與p相同的子字串,
如果子字串的排列與p的排列相同,
那子字串就是重組字,
但是因為要做相當於「子字串個數」的排列次數,
時間上相當耗時,
程式執行時間整整花了8768 ms,
還好此題的時限非常寬鬆沒有算小馬超時

python程式碼暴力解,8768 ms

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        P = sorted(p)
        ans = []
        for i in range(len(s)-len(p)+1):
            if(sorted(s[i:i+len(p)])==P):
                ans.append(i)
        return ans

python程式碼用Counter,164 ms

但是一支程式執行8768 ms,相當於8秒鐘,
怎麼想都實在是太慢了,
還好另外想了一招,
執行速度足足快了50倍左右,
小馬想到判斷是不是anagram,
除了檢查排列是否一樣,
還可以用數個數的方式呀

例如說ateeat
如果去數字母個數的話,都是「a 1個、e 1個、t 1個」,
用Counter可以統計每個單字的個數,
好處是遍歷字串時,
可以很容易的去刪除前一個字,增加新的一個字,
不用每次都重新把子字串抓出來重新排列

優化後的程式碼如下:

from collections import Counter
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        P = Counter(p)
        subStr = Counter(s[:len(p)])
        ans = [0] if subStr == P else []
        for i in range(len(s)-len(p)):
            subStr[s[i]]-=1
            if subStr[s[i]]==0: #如果元素個數為0,記得刪除
                del subStr[s[i]]
            subStr[s[i+len(p)]]+=1
            if(subStr == P):
                ans.append(i+1)
        return ans

尚未有邦友留言

立即登入留言