從LeetCode學演算法 - 76 Hash Table (5)

0290. Word Pattern (Easy)

Question

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a ** non-empty** word in str.

Example 1

1
2
Input: pattern = "abba", str = "dog cat cat dog"
Output: true

Example 2

1
2
Input:pattern = "abba", str = "dog cat cat fish"
Output: false

Example 3

1
2
Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false

Example 4

1
2
Input: pattern = "abba", str = "dog dog dog dog"
Output: false

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.

分析/解題

給定一個pattern和一個字串str，檢查str是否遵循pattern的模式。
簡單來說，就是str的每一段字的重複或不重複模式，
都要能被pattern裡的"abba"這樣的每個字母去對應 的方式來表達出來。
看到這邊，有沒有覺得很像LeetCode最開始的那個Two Sum?
我們每次想要將一個pattern內的字母去對應到str的一段字串，
而重複的狀況應該要有相同的對應。

那不就是key-value的對應方式嗎?

所以想法就很簡單了：

建立一個Hash Table名為map(Java的HashMap或Python的Dictionary)
先檢查pattern的段數和str的段數是否相同 ，若否則直接回傳false
依序按段取出 pattern和對應的str的分段，檢查以下性質：
(下面pattern均作為key，str的分段均作為value)
若key不存在且value不存在->將**(key, value)** 放入map
若key不存在且value存在->回傳false (** 表示別人先對應到它了**)
若key存在且value不對->回傳false (** 表示該key已經被占用掉**)

請留意後面的兩個false的狀況，
我們可以對照Example 2 跟Example 3 ，
因為有些可能是前面某個key或某個value已經達成對應關係了，
後續如果出現對不上的狀況，就表示整個對應關係無法成立囉！

依此，寫成程式碼如下：

Java

Java的部分，
可以使用HashMap的containsKey/containsValue/get，
以及字串的split/equals函式，來協助判斷的工作。

Python

Python方面，同樣有split可以使用，
其他使用dict的in/not in及values()等簡單的存取方式即可。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(N)，準確來說應該是看len(str)來決定N)

「如果限制使用split呢？」
(進行依字元掃瞄過整個陣列，碰到空白再輸出成字串(list或arraylist)即可)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(額滿即截止)： ** https://hiskio.com/courses/319?promo_code=VEQZV7E**