890-查找和替換模式

haobowd 發布于2019-08-19 10:59 / 2074人閱讀

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

前言

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

你有一個單詞列表 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 映射到同一個字母。

解題思路

這道題目其實就是需要用一個數據結構去描述單詞和模式之間的映射關系，而且模式和單詞中的字母的關系是一對一，所以可以直接使用Map去解決這個問題。

實現代碼

    /**
     * 查找和替換模式
     * @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;
            //用于存儲映射關系的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)) {//模式中的字母是否已經映射已經被映射
                    char value = map.get(p);
                    if (value != w) {
                        match = false;
                        break;
                    }
                } else {
                    if(map.containsValue(w)){//判斷單詞中的字母是否被映射，防止模式多個字母都映射單詞中的同一個字母
                        match = false;
                        break;
                    }else {
                        map.put(p, w);
                    }
                }
            }
            if (match) {
                result.add(word);
            }
        }
        return result;
    }

GPU云服務器云服務器查找替換 php排序和查找 utm模式和防火墻模式重構和設計模式

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76797.html

Javascript 正則表達式

摘要：正則表達式對象通過內置對象支持正則表達式。做法很簡單，就是在量詞后添加一個即可分組分組或分組取值前瞻正則表達式是從文本頭部向尾部解析。正則表達式 REGEXP對象 javascript通過內置對象Regexp支持正則表達式。兩種方法來創建Regexp對象。 1、字面量 var reg = /d{4}/g; // g 表示進行全局替換 2、構造函數 var reg = new R...

woshicixide 2019-08-23 10:40 評論0 收藏0
【Python3】基本數據類型-字符串（str）

摘要：字符串常用功能移除空白分割長度索引切片下面來詳細介紹下字符串首字母大寫將所有大寫變小寫支持多種國家語言將大寫變成小寫只支持英文文本居中參數表示總長度參數空白處填充的字符長度為左右填充，包含自身長度表示傳入之在字符串中出現的次數參數要查找的值字符串常用功能: 移除空白分割長度索引切片下面來詳細介紹下 ~ capitalize 字符串首字母大寫 name = xmzncc ...

Awbeci 2019-07-31 10:56 評論0 收藏0
JavaScript正則進階之路——活學妙用奇淫正則表達式

摘要：正則大法好，正則大法好，正則大法好，重要的事情說三遍。第二部分，這個部分是整個表達式的關鍵部分。學習正則如果還沒有系統學習正則表達式，這里提供一些網上經典的教程供大家學習。正則表達式使用單個字符串來描述匹配一系列匹配某個句法規則的字符串。原文收錄在我的 GitHub博客 (https://github.com/jawil/blog) ，喜歡的可以關注最新動態，大家一起多交流學習，共同...

BearyChat 2019-08-29 12:40 評論0 收藏0
JavaScript正則進階之路——活學妙用奇淫正則表達式

摘要：正則大法好，正則大法好，正則大法好，重要的事情說三遍。第二部分，這個部分是整個表達式的關鍵部分。學習正則如果還沒有系統學習正則表達式，這里提供一些網上經典的教程供大家學習。正則表達式使用單個字符串來描述匹配一系列匹配某個句法規則的字符串。原文收錄在我的 GitHub博客 (https://github.com/jawil/blog) ，喜歡的可以關注最新動態，大家一起多交流學習，共同...

APICloud 2019-08-20 16:52 評論0 收藏0