圖解 | LeetCode #290 單詞規(guī)律

????關(guān)注后回復(fù) “進(jìn)群” ，拉你進(jìn)程序員交流群????

作者丨木兄

來源丨編程狂想曲

你好，我是微木。

今天分享的內(nèi)容是LeetCode中290.單詞規(guī)律 簡單 這個題目。

題目描述：

給定一種規(guī)律 pattern 和一個字符串str ，判斷str是否遵循相同的規(guī)律。

這里的遵循指完全匹配，例如，pattern里的每個字母和字符串 str 中的每個非空單詞之間存在著雙向連接的對應(yīng)規(guī)律。

示例1:

輸入: pattern = "abba", str = "dog cat cat dog"

輸出: true
示例2:
輸入: pattern = "abba", str = "dog cat cat fish"
輸出: false

思路分析
   

    根據(jù)示例分析可知，判斷str是否遵循相同的規(guī)律，就是判斷str中的每個單詞是否和pattern中的每個字符有唯一的對應(yīng)關(guān)系，即映射關(guān)系。
   
   

    在示例1中，字符a對應(yīng)單詞dog，字符b對應(yīng)單詞cat是一一映射關(guān)系；在示例2中，第一個字符a對應(yīng)單詞dog，第二個字符a對應(yīng)單詞fish，不是一一映射關(guān)系。
   
   

    因此，整體求解思路就是借助map來判斷patter和str之間是否是一一對應(yīng)的映射關(guān)系。
   
   

    若pattern和str是一一對應(yīng)關(guān)系，則pattern中的字符個數(shù)和str中的單詞個數(shù)是相同的。因此，當(dāng)pattern中的字符個數(shù)和str中的單詞個數(shù)不同時，結(jié)果肯定為false。如下圖：
   
   

    
   
   

    當(dāng)pattern中的字符個數(shù)和str中的單詞個數(shù)相同時，接著就是遍歷patter和str：
   
   

    若當(dāng)前考察的pattern中的字符在map中不存在，但當(dāng)前考察的str中的單詞在map中存在，則表明已有其它字符和該單詞對應(yīng)，即多個字符對應(yīng)同一個單詞，直接返回false。如下圖，字符a和字符b都對應(yīng)單詞dog；
   
   

    
   
   

    若當(dāng)前考察的pattern中的字符在map中不存在，且當(dāng)前考察的str中的單詞在map中也存在，則將pattern中的字符作為key，str中的單詞作為value存入map，建立兩者間的映射關(guān)系；
   
   

    若當(dāng)前考察的pattern中的字符在map中存在，但其對應(yīng)的value和str中當(dāng)前考察的單詞不相同，則表明同一字符對應(yīng)著多個單詞，因此返回false。如下圖，字符a既對應(yīng)單詞dog又對應(yīng)單詞cat；
   
   

    
   
   

    若上述考察沒有返回，則表明pattern中的字符和str中的單詞是一一對應(yīng)關(guān)系，返回true。
   
   

    代碼實(shí)現(xiàn)：
   
   

    
   

-End-

最近有一些小伙伴，讓我?guī)兔φ乙恍?nbsp;面試題 資料，于是我翻遍了收藏的 5T 資料后，匯總整理出來，可以說是程序員面試必備！所有資料都整理到網(wǎng)盤了，歡迎下載！

點(diǎn)擊??卡片，關(guān)注后回復(fù)【面試題】即可獲取

在看點(diǎn)這里好文分享給更多人↓↓