Medium

题目描述

给定字符串列表 words 和字符串 pattern，返回匹配 pattern 的 words[i] 列表。你可以按任意顺序返回答案。

如果存在字母的排列 p，使得将 pattern 中的每个字母 x 替换为 p(x) 后得到所需的单词，则单词与模式匹配。

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

示例 1:

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

示例 2:

输入: words = ["a","b","c"], pattern = "a"
输出: ["a","b","c"]

约束条件:

  • 1 <= pattern.length <= 20
  • 1 <= words.length <= 50
  • words[i].length == pattern.length
  • pattern 和 words[i] 都是小写英文字母

解题思路

这道题的关键是理解"双射"的概念：模式中的每个字符都必须与单词中的字符建立一对一的映射关系。

解题思路：

  1. 双向映射验证法：对于模式和单词，需要建立两个映射关系

    • 模式字符到单词字符的映射
    • 单词字符到模式字符的映射
    • 两个映射都必须保持一致性，确保是双射关系

  2. 字符标准化法：将模式和单词都转换为标准化形式

    • 对每个字符串，将其转换为字符首次出现的位置序列
    • 比较转换后的序列是否相同

推荐解法：字符标准化法更简洁，代码更易理解。我们将每个字符串转换为其字符首次出现的索引序列，如果两个字符串的标准化形式相同，则它们匹配。

例如："abb" 转换为 [0,1,1]，"mee" 转换为 [0,1,1]，两者相同，所以匹配。

代码实现

class Solution {
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> result;
        vector<int> patternNorm = normalize(pattern);
        
        for (const string& word : words) {
            if (normalize(word) == patternNorm) {
                result.push_back(word);
            }
        }
        
        return result;
    }
    
private:
    vector<int> normalize(const string& str) {
        unordered_map<char, int> charToIndex;
        vector<int> normalized;
        int nextIndex = 0;
        
        for (char c : str) {
            if (charToIndex.find(c) == charToIndex.end()) {
                charToIndex[c] = nextIndex++;
            }
            normalized.push_back(charToIndex[c]);
        }
        
        return normalized;
    }
};

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        def normalize(s):
            char_to_index = {}
            normalized = []
            next_index = 0
            
            for c in s:
                if c not in char_to_index:
                    char_to_index[c] = next_index
                    next_index += 1
                normalized.append(char_to_index[c])
            
            return tuple(normalized)
        
        pattern_norm = normalize(pattern)
        result = []
        
        for word in words:
            if normalize(word) == pattern_norm:
                result.append(word)
        
        return result

public class Solution {
    public IList<string> FindAndReplacePattern(string[] words, string pattern) {
        var result = new List<string>();
        var patternNorm = Normalize(pattern);
        
        foreach (string word in words) {
            if (Normalize(word).SequenceEqual(patternNorm)) {
                result.Add(word);
            }
        }
        
        return result;
    }
    
    private int[] Normalize(string str) {
        var charToIndex = new Dictionary<char, int>();
        var normalized = new int[str.Length];
        int nextIndex = 0;
        
        for (int i = 0; i < str.Length; i++) {
            char c = str[i];
            if (!charToIndex.ContainsKey(c)) {
                charToIndex[c] = nextIndex++;
            }
            normalized[i] = charToIndex[c];
        }
        
        return normalized;
    }
}

/**
 * @param {string[]} words
 * @param {string} pattern
 * @return {string[]}
 */
var findAndReplacePattern = function(words, pattern) {
    function matches(word, pattern) {
        if (word.length !== pattern.length) return false;
        
        let wordToPattern = new Map();
        let patternToWord = new Map();
        
        for (let i = 0; i < word.length; i++) {
            let w = word[i];
            let p = pattern[i];
            
            if (wordToPattern.has(w)) {
                if (wordToPattern.get(w) !== p) return false;
            } else {
                wordToPattern.set(w, p);
            }
            
            if (patternToWord.has(p)) {
                if (patternToWord.get(p) !== w) return false;
            } else {
                patternToWord.set(p, w);
            }
        }
        
        return true;
    }
    
    return words.filter(word => matches(word, pattern));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n × m)n 是单词数量，m 是单词长度，每个单词都需要进行标准化处理
空间复杂度O(m)每次标准化需要 O(m) 的哈希表空间和数组空间

相关题目