890. 查找和替换模式：

你有一个单词列表 words 和一个模式 pattern，你想知道 words 中的哪些单词与模式匹配。

如果存在字母的排列 p ，使得将模式中的每个字母 x 替换为 p(x) 之后，我们就得到了所需的单词，那么单词与模式是匹配的。

（回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）

返回 words 中与给定模式匹配的单词列表。

你可以按任何顺序返回答案。

样例 1：

输入：
	words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
	
输出：
	["mee","aqq"]
	
解释：
	"mee" 与模式匹配，因为存在排列 {a -> m, b -> e, ...}。
	"ccc" 与模式不匹配，因为 {a -> c, b -> c, ...} 不是排列。
	因为 a 和 b 映射到同一个字母。

提示：

• 1 <= words.length <= 50
• 1 <= pattern.length = words[i].length <= 20

分析

• 面对这道算法题目，二当家的陷入了沉思。
• 需要一个结构来存储映射关系，在遍历过程中判断是否有映射，如果没有就生成一个映射，如果有就判断和本次的字符是否一致，因为不允许两个字母映射到同一个字母。
• 换个角度，我们不存储字母映射到的新字母，而是存储字母最后一次出现的位置，那么单词字母和模式字母要么第一次出现，要么之前出现的位置一致，就保证了字母之间一一映射，不会出现两个字母映射到同一个字母。

题解

rust

impl Solution {
    pub fn find_and_replace_pattern(words: Vec<String>, pattern: String) -> Vec<String> {
        words.into_iter().filter(|w| {
			// 字符最后一次出现的位置
            let mut wc_index = vec![0; 26];
            let mut pc_index = vec![0; 26];
            for i in 0..pattern.len() {
                let wc = (w.as_bytes()[i] - 'a' as u8) as usize;
                let pc = (pattern.as_bytes()[i] - 'a' as u8) as usize;
                if wc_index[wc] != pc_index[pc] {
                    return false;
                } else {
                    wc_index[wc] = i + 1;
                    pc_index[pc] = i + 1;
                }
            }
            return true;
        }).collect()
    }
}

go

func findAndReplacePattern(words []string, pattern string) []string {
    var ans []string

	for _, w := range words {
		wcIndex := make([]int, 26)
		pcIndex := make([]int, 26)
		isMatch := true
		for i := 0; i < len(pattern); i++ {
			wc := w[i] - 'a'
			pc := pattern[i] - 'a'
			if wcIndex[wc] != pcIndex[pc] {
				isMatch = false
				break
			} else {
				wcIndex[wc] = i + 1
				pcIndex[pc] = i + 1
			}
		}
		if isMatch {
			ans = append(ans, w)
		}
	}

	return ans
}

c++

class Solution {
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> ans;

        for (string &w: words) {
            int wcIndex[26] = {};
            int pcIndex[26] = {};
            bool isMatch = true;
            for (int i = 0; i < pattern.length(); ++i) {
                int wc = w[i] - 'a';
                int pc = pattern[i] - 'a';
                if (wcIndex[wc] != pcIndex[pc]) {
                    isMatch = false;
                    break;
                } else {
                    wcIndex[wc] = i + 1;
                    pcIndex[pc] = i + 1;
                }
            }
            if (isMatch) {
                ans.emplace_back(w);
            }
        }

        return ans;
    }
};

java

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> ans = new ArrayList<>();

        for (String w : words) {
            int[] wcIndex = new int[26];
            int[] pcIndex = new int[26];
            boolean isMatch = true;
            for (int i = 0; i < pattern.length(); ++i) {
                int wc = w.charAt(i) - 'a';
                int pc = pattern.charAt(i) - 'a';
                if (wcIndex[wc] != pcIndex[pc]) {
                    isMatch = false;
                    break;
                } else {
                    wcIndex[wc] = i + 1;
                    pcIndex[pc] = i + 1;
                }
            }
            if (isMatch) {
                ans.add(w);
            }
        }

        return ans;
    }
}

python

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        ans = []
        for w in words:
            wc_index = [0] * 26
            pc_index = [0] * 26
            is_match = True
            for i in range(len(pattern)):
                wc = ord(w[i]) - 97
                pc = ord(pattern[i]) - 97
                if wc_index[wc] != pc_index[pc]:
                    is_match = False
                    break
                else:
                    wc_index[wc] = i + 1
                    pc_index[pc] = i + 1
            if is_match:
                ans.append(w)
        return ans

原题传送门：https://leetcode.cn/problems/find-and-replace-pattern/

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~