题目地址:https://leetcode.com/problems/find-and-replace-pattern/description/

题目描述

Youhave a list of words and a pattern, and you want to know which words in words matches the pattern.

Aword matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.

(Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.)

Return a list of the words in words that match the given pattern.

Youmay return the answer in any order.

Example 1:

Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. 
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation,
since a and b map to the same letter.

Note:

1、 1<=words.length<=50;
2、 1<=pattern.length=words[i].length<=20;

题目大意

我觉得应该把题目中的permutation理解为“映射”更为合适。

这样的话,题目意思就是找出words中所有满足映射关系的单词。映射关系由pattern给出,即要求words中的单词和pattern中的每个字符的对应关系应该完全一致。

解题方法

字典+set

既然考到映射,那么应该是使用HashMap来搞定,直接把映射一一的放入map中,如果出现过这个映射的话,就看新的对应关系和原来的映射是否相同。

代码中使用了set,这个set很重要,因为这个保证了不会出现ccc对应abb这种。

注意题目中给出了一个细节,就是words里面的每个word都和pattern长度相同,省去了判断长度的过程。

代码如下:

class Solution(object):
    def findAndReplacePattern(self, words, pattern):
        """
        :type words: List[str]
        :type pattern: str
        :rtype: List[str]
        """
        ans = []
        set_p = set(pattern)
        for word in words:
            if len(set(word)) != len(set_p):
                continue
            fx = dict()
            equal = True
            for i, w in enumerate(word):
                if w in fx:
                    if fx[w] != pattern[i]:
                        equal = False
                        break
                fx[w] = pattern[i]
            if equal:
                ans.append(word)
        return ans

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

单字典

如果使用单字典,需要判断word向pattern的映射和pattern向word的映射。这个代码就没有什么好说的了。

Python代码如下:

class Solution(object):
    def findAndReplacePattern(self, words, pattern):
        """
        :type words: List[str]
        :type pattern: str
        :rtype: List[str]
        """
        res = []
        for word in words:
            if len(word) != len(pattern): continue
            d = dict()
            isMatch = True
            for i, c in enumerate(pattern):
                if c in d:
                    if d[c] != word[i]:
                        isMatch = False
                        break
                d[c] = word[i]
            d = dict()
            for i, c in enumerate(word):
                if c in d:
                    if d[c] != pattern[i]:
                        isMatch = False
                        break
                d[c] = pattern[i]
            if isMatch:
                res.append(word)
        return res

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

C++代码如下:

class Solution {
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> res;
        for (string& word : words) {
            bool isMatch = true;
            map<char, char> d;
            for (int i = 0; i < word.size(); i++) {
                if (d.count(word[i])) {
                    if (d[word[i]] != pattern[i]) {
                        isMatch = false;
                        break;
                    }
                }
                d[word[i]] = pattern[i];
            }
            d.clear();
            for (int i = 0; i < word.size(); i++) {
                if (d.count(pattern[i])) {
                    if (d[pattern[i]] != word[i]) {
                        isMatch = false;
                        break;
                    }
                }
                d[pattern[i]] = word[i];
            }
            if (isMatch) res.push_back(word);
        }
        return res;
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发