『LeetCode』890 查找和替换模式

题目

你有一个单词列表 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 映射到同一个字母。

提示：

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

题解

【查找和替换模式】简单模拟

模拟

简单来说，题目的要求就是要我们检测 word 和 pattern 是否满足一一对应的双射关系，只需对每个单词逐字母的构建一个由 word 到 pattern 的字母映射关系，再检查该关系是否是双射即可。

这里可以有两种方法进行检查：

构建 word 到 pattern 和 pattern 到 word 的映射关系，检查二者是否都是单射。
只构建 word 到 pattern 的映射关系，检查其是否是单射并且是否有多对一的映射关系。

方法一：

# Code language: Python
class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        ans = list()
        a = ord('a')
        for word in words:
            m1 = [None for _ in range(26)]
            m2 = [None for _ in range(26)]
            for i, j in zip(word, pattern):
                x, y = ord(i) - a, ord(j) - a
                if m1[x] is None:
                    m1[x] = y
                if m2[y] is None:
                    m2[y] = x
                if m1[x] != y or m2[y] != x:
                    break
            else:
                ans.append(word)
        return ans

// Code language: Java
class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> ans = new ArrayList<>();
        int n = pattern.length();
        int[] m1 = new int[26], m2 = new int[26];
        loop: for (String word: words) {
            Arrays.fill(m1, -1); Arrays.fill(m2, -1);
            for (int i = 0; i < n; ++i) {
                int x = word.charAt(i) - 'a', y = pattern.charAt(i) - 'a';
                if (m1[x] == -1) m1[x] = y;
                if (m2[y] == -1) m2[y] = x;
                if (m1[x] != y || m2[y] != x) continue loop;
            }
            ans.add(word);
        }
        return ans;
    }
}

// Code language: C++
class Solution {
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> ans;
        int n = pattern.size();
        int m1[26], m2[26];
        for (string& word: words) {
            memset(m1, -1, sizeof(m1)), memset(m2, -1, sizeof(m2));
            bool p = true;
            for (int i = 0; i < n; ++i) {
                int x = word[i] - 'a', y = pattern[i] - 'a';
                if (m1[x] == -1) m1[x] = y;
                if (m2[y] == -1) m2[y] = x;
                if (m1[x] != y || m2[y] != x) {
                    p = false; break;
                }
            }
            if (p) ans.emplace_back(word);
        }
        return ans;
    }
};

// Code language: JavaScript
/**
 * @param {string[]} words
 * @param {string} pattern
 * @return {string[]}
 */
var findAndReplacePattern = function (words, pattern) {
    var ans = new Array();
    var n = pattern.length, m = words.length, a = 'a'.charCodeAt(0);
    var m1 = new Array(), m2 = new Array();
    var word;
    for (let idx = 0; idx < m; ++idx) {
        word = words[idx];
        for (let i = 0; i < 26; ++i) {
            m1[i] = -1;
            m2[i] = -1;
        }
        let p = true;
        for (let i = 0; i < n; ++i) {
            let x = word.charCodeAt(i) - a, y = pattern.charCodeAt(i) - a;
            if (m1[x] == -1) m1[x] = y;
            if (m2[y] == -1) m2[y] = x;
            if (m1[x] != y || m2[y] != x) {
                p = false;
                break;
            }
        }
        if (p) ans.push(word);
    }
    return ans;
};

方法二：

# Code language: Python
class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        ans = list()
        a = ord('a')
        for word in words:
            m = [None for _ in range(26)]
            for i, j in zip(word, pattern):
                x, y = ord(i) - a, ord(j) - a
                if m[x] is None:
                    m[x] = y
                if m[x] != y:
                    break
            else:
                s = set()
                for t in m:
                    if t is not None and t in s:
                        break
                    s.add(t)
                else:
                    ans.append(word)
        return ans

// Code language: Java
class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> ans = new ArrayList<>();
        int n = pattern.length();
        int[] m1 = new int[26], m2 = new int[26];
        loop: for (String word: words) {
            Arrays.fill(m1, -1); Arrays.fill(m2, -1);
            for (int i = 0; i < n; ++i) {
                int x = word.charAt(i) - 'a', y = pattern.charAt(i) - 'a';
                if (m1[x] == -1) m1[x] = y;
                if (m1[x] != y) continue loop;
            }
            for (int m: m1) {
                if (m == -1) continue;
                if (m2[m] != -1) continue loop;
                m2[m] = 1;
            }
            ans.add(word);
        }
        return ans;
    }
}

// Code language: C++
class Solution {
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> ans;
        int n = pattern.size();
        int m1[26], m2[26];
        for (string& word: words) {
            memset(m1, -1, sizeof(m1)), memset(m2, -1, sizeof(m2));
            bool p = true;
            for (int i = 0; i < n; ++i) {
                int x = word[i] - 'a', y = pattern[i] - 'a';
                if (m1[x] == -1) m1[x] = y;
                if (m1[x] != y) {
                    p = false; break;
                }
            }
            if (!p) continue;
            for (int i = 0; i < 26; ++i) {
                int m = m1[i];
                if (m == -1) continue;
                if (m2[m] != -1) {
                    p = false; break;
                }
                m2[m] = 1;
            }
            if (p) ans.emplace_back(word);
        }
        return ans;
    }
};

时间复杂度: \(O(nm)\), 其中 \(n\) 表示最大单词长度，\(m\) 表示 words 的长度
空间复杂度: \(O(26)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』890 查找和替换模式

题目

标签

题解

模拟