每天一道leetcode890-查找和替換模式
- 2019 年 10 月 4 日
- 筆記
昨天的題解
題目
每天一道leetcode890-查找和替換模式 分類：字元串
題目詳述
你有一個單詞列表 words 和一個模式 pattern，你想知道 words 中的哪些單詞與模式匹配。
如果存在字母的排列 p ，使得將模式中的每個字母 x 替換為 p(x) 之後，我們就得到了所需的單詞，那麼單詞與模式是匹配的。
（回想一下，字母的排列是從字母到字母的雙射：每個字母映射到另一個字母，沒有兩個字母映射到同一個字母。）
返回 words 中與給定模式匹配的單詞列表。
你可以按任何順序返回答案。
示例：
輸入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb" 輸出：["mee","aqq"] 解釋： "mee" 與模式匹配，因為存在排列 {a -> m, b -> e, …}。 "ccc" 與模式不匹配，因為 {a -> c, b -> c, …} 不是排列。 因為 a 和 b 映射到同一個字母。
題目詳解
思路
- 因為是一一對應的關係，所以使用hashmap，依次比較abb與word中的每一個字元，比如說abb與abc,a與a對應存入hahsmap，b與b對應存入hashmap,第3對，b是key已經存入hashmap中了，讀取hashmap發現value是c所以一個b對應了b和c所以匹配失敗
- 上述情況有個漏洞就是，比如abb與ccc,a和c存入hashmap，b和c存入，然後最後一個b發現已經在hashmap中，一讀取出來b對應的value值是c與對應的第三對b-c是一樣的，這個時候會在上述情況成立，而把ccc也保留
- 如何解決，那麼就是又建立一個hashmap，稱為hashmap2,這個hashmap用來每次保存反向的，反向啥意思就是上述hashmap存a和c，我hashmap2存c和a,這樣在下一次hashmap1要存b和c的時候成立，但是hashmap2存c-b不成立了，因為hashmap2已經存了c-a這個時候直接返回false用兩個hashmap就可以解決了。
class Solution { public static List<String> findAndReplacePattern(String[] words, String pattern) { List<String> result = new ArrayList<>();//返回結果 char [] patternArray = pattern.toCharArray();//字元串轉字元數組 for(int i=0;i<words.length;i++)//遍歷每一個words中的字元串 { char [] wordArray = words[i].toCharArray(); boolean flag = true;//標記，為true說明匹配 if(wordArray.length == patternArray.length)//匹配肯定長度要相等 { HashMap<Character,Character> judge = new HashMap<>();//hashmap1 HashMap<Character,Character> judge2 = new HashMap<>();//反向比較hashmap2 for(int j=0;j<pattern.length();j++)//遍歷模式串中的每一個字元 { if(judge.containsKey(patternArray[j]) == false) {//判斷key中是否存在這個字元，不存在hashmap1就添加key-value judge.put(patternArray[j],wordArray[j]); if(judge2.containsKey(wordArray[j]) == false) {//這個if else的作用就是思路中的hashmap2的作用了 judge2.put(wordArray[j],patternArray[j]);//不存在就添加 }else { if(judge2.get(wordArray[j]) != patternArray[j]){ flag = false;//存在的話就去判斷是不是相等的，不相等就不匹配 break; } } }else {//存在的話 去hashmap中找這個字元與現有的字元是否相等 //不相等，說明存在了（a-c a-b 一個a對應兩個字元）直接返回false,不匹配 if(judge.get(patternArray[j]) != wordArray[j]) { flag = false; break; } } } if(flag) { result.add(words[i]); } } } return result; } }
