LeetCode解題筆記#2-Vowel Spellchecker

Vowel Spellchecker 以我的程度我認為真的偏難,整體思路必須得非常清楚才解得出來,我一開始的思路沒有成功,最後是參考網路上的答案才解出來的,以下呢我會講解成功的思路以及失敗的思路怎麼做延伸!

Vowel Spellchecker 題目詳解

Vow Spellchecker一樣幫大家做英翻中的話就是,這個題目要檢查query這個陣列裡面所有的值和wordlist這個值裡面做比較,而比較過後要根據狀況將query裡面的值換成wordlist裡面match的值,這邊比較難的會是看懂題目翻譯的條件,在這邊幫大家整理成三個條件

  1. 完美match:也就是整體字串都長得一模一樣的match值
  2. 不論大小寫match: 也就是假設將字串都換成小寫的話 會長得一模一樣的match值 ex: Kite 和 kiTe就會是一樣
  3. 不論母音和大小寫的match:除了上個條件你的位置是母音的話不管是否match直接跳過 ex: Keti 和 kato是一樣

整理出以上的條件對於解題思路非常重要,因為這個題目需要用到大量的for迴圈來核對match,但如果你思路不夠清晰很可能會讓程式卡在雙迴圈或甚至三迴圈中不知道怎麼跳脫,以下先講解我的思路

失敗的思路

首先我一樣找到三種狀況了,但這段程式碼的問題會是在,我嘗試在queries和wordlist組成的雙迴圈中直接比對並解決三種條件,這樣的問題就會是在,因為被限制在雙迴圈的框架下,要同時做資料的處理,譬如轉換uppercase之後做比較,並且第三個條件是必須要做特殊處理才能比較的,大家應該都能想像得到,在這樣的狀況下,雙迴圈的限制就會導致在寫程式時綁手綁腳,到後面甚至會寫不下去,這是這次解題我的思路失敗的地方。

成功的思路

所以我們從失敗的思路中整理出兩個點,第一個是我們必須要對資料做處理才能進行比對,第二個是條件3需要經過特殊處理才能進行比對,那這個時候最好的方式,就會是我們將要處理的資料延伸成三個陣列,也就是將三個條件分別寫成三個陣列,我們先來看程式碼

class Solution:
    def devowel(self,word): #去母音的方式 kite > k*t*
        t=''
        for ch in word:
            if(ch in 'aeiou'):
                t+='*' #將母音的值轉換成*方便一致
            else:
                t+=ch  #正常轉換
        return t
    
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        #題目能夠分為三個條件來判斷要轉換成什麼值
        #1.完美match 2.不看字母大小寫的話match 3.不看母音位置只看子音的話的match
        #將wordlist內的值 根據三個條件換成 在這三個條件上的值的話會是怎樣 例如第二個條件 KiTe -> kite 
        words_perfect=set(wordlist)
        words_cap={}
        words_vow={}
        for word in wordlist:#轉換第二第三條件
            t=word.lower() #由於二三條件已經不考慮大小寫所以直接換成lower case
            #此處利用字典的方式是因為,要透過鍵比較,然後要放進去anwer的為鍵值,而這裡會牽扯到如果setdefault
            #和這個題目的互動,因為我們知道他會先找第一個match的值當作答案,而在第二和第三個條件的狀況下,word
            #的大小值
            words_cap.setdefault(t,word) #检查dic中是否有t这个键,如果没有,则添加,word是键值
            words_vow.setdefault(self.devowel(t),word)   
        print(words_cap)
        print(words_vow)
        res=[]
        for query in queries:
            if(query in words_perfect):
                res.append(query)
                continue
            query=query.lower()
            if(query in words_cap): #檢查鍵而已 不會檢查到鍵值,之後放入word
                print(words_cap[query])
                res.append(words_cap[query])
                continue
            query=self.devowel(query)
            if(query in words_vow):
                res.append(words_vow[query])
                continue
            res.append('')
        return res

可以看到上面的程式碼將程式分成了兩個部分,一個是比對,而比對的部分就是非常簡單,原因是他已經先將三個條件各自化為一個wordlist,所以在比對時就用各自比對的方式加入到answerlist裡面並且用continue來截斷避免重複比對的問題,而再來就會是處理資料的部分,第一個條件不需要處理,而第二個條件則是直接將wordlist轉換成lowercase就可以了,第三個條件就會是比較特別的地方了。

由於是母音的位置不需要去做內容的比對,所以在處理的時候只要將他換成其他的符號就好,這裡會是”*”,那可能會有人有疑惑,換成*的話等等跟querylist比對怎麼會成功呢?一個是k*t*,一個是keto,怎麼看都不會match啊,在這裏使用者在比對前提前將querylist的內容也放進去母音轉換成”*”的function,這樣就完美解決了這些狀況了。提交過後得到了以下的跑分,這次不以速度為參考而以佔據的memory。

看了以下占memory比最小的答案,基本上是由失敗的思路延伸出去但整體更清晰的寫法,也就是不延伸出新的陣列來處理,我認為那樣的寫法雖然跑分高,但整體程式看起來就很不清晰,所以我認為更好的方式還是我參考的思路,整體更清晰也更簡單,今天的解題就到這裡,我認為這題的難度算是高的,有很多小細節和思路不理清楚的話整體會非常難寫。

馬上看–> Leetcode解題筆記#1-Hamming Weight

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。