890-查找和替換模式

haobowd 發(fā)布于2019-08-19 10:59 / 2081人閱讀

摘要：前言的的題目查找和替換模式，原題目描述如下你有一個(gè)單詞列表和一個(gè)模式，你想知道中的哪些單詞與模式匹配。如果存在字母的排列，使得將模式中的每個(gè)字母替換為之后，我們就得到了所需的單詞，那么單詞與模式是匹配的。

前言

LeetCode的Weekly Contest 98的題目查找和替換模式，原題目描述如下：

你有一個(gè)單詞列表 words 和一個(gè)模式  pattern，你想知道 words 中的哪些單詞與模式匹配。
如果存在字母的排列 p ，使得將模式中的每個(gè)字母 x 替換為 p(x) 之后，我們就得到了所需的單詞，那么單詞與模式是匹配的。
（回想一下，字母的排列是從字母到字母的雙射：每個(gè)字母映射到另一個(gè)字母，沒有兩個(gè)字母映射到同一個(gè)字母。）
返回 words 中與給定模式匹配的單詞列表。
你可以按任何順序返回答案。示例：
輸入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
輸出：["mee","aqq"]
解釋：
"mee" 與模式匹配，因?yàn)榇嬖谂帕?{a -> m, b -> e, ...}。
"ccc" 與模式不匹配，因?yàn)?{a -> c, b -> c, ...} 不是排列。
因?yàn)?a 和 b 映射到同一個(gè)字母。

解題思路

這道題目其實(shí)就是需要用一個(gè)數(shù)據(jù)結(jié)構(gòu)去描述單詞和模式之間的映射關(guān)系，而且模式和單詞中的字母的關(guān)系是一對(duì)一，所以可以直接使用Map去解決這個(gè)問題。

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

    /**
     * 查找和替換模式
     * @param words
     * @param pattern
     * @return
     */
    public List findAndReplacePattern(String[] words, String pattern) {
        List result = new ArrayList<>();
        char[] patternChars = pattern.toCharArray();
        for (String word : words) {
            char[] wordChars = word.toCharArray();
            //是否匹配
            boolean match = true;
            //用于存儲(chǔ)映射關(guān)系的Map
            Map map = new HashMap<>();
            for (int i = 0; i < patternChars.length; i++) {
                char p = patternChars[i];
                char w = wordChars[i];
                if (map.containsKey(p)) {//模式中的字母是否已經(jīng)映射已經(jīng)被映射
                    char value = map.get(p);
                    if (value != w) {
                        match = false;
                        break;
                    }
                } else {
                    if(map.containsValue(w)){//判斷單詞中的字母是否被映射，防止模式多個(gè)字母都映射單詞中的同一個(gè)字母
                        match = false;
                        break;
                    }else {
                        map.put(p, w);
                    }
                }
            }
            if (match) {
                result.add(word);
            }
        }
        return result;
    }