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

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

作者丨木兄

來源丨編程狂想曲

你好，我是微木。

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

題目描述：

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

這里的遵循指完全匹配，例如，pattern里的每個(gè)字母和字符串 str 中的每個(gè)非空單詞之間存在著雙向連接的對(duì)應(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中的每個(gè)單詞是否和pattern中的每個(gè)字符有唯一的對(duì)應(yīng)關(guān)系，即映射關(guān)系。
   
   

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

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

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

    
   
   

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

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

    
   
   

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

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

    
   
   

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

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

    
   

-End-

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

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

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