LeetCode890-查找和替换模式

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/find-and-replace-pattern/

中文链接：https://leetcode-cn.com/problems/find-and-replace-pattern/

题目详述

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

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

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

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

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

示例：

1
2
3
4
5
6
输入：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

题目详解

方法一：

  • 两个字符串的对应关系是相同的，就是匹配的。
  • 对 words 来说，如果位置 i 和 j 对应字符相同，则 pattern 位置 i 和 j 对应字符也也应该相同，否则不匹配。
  • 对 words 来说，如果位置 i 和 j 对应字符不同，则 pattern 位置 i 和 j 对应字符也也应该不同，否则不匹配。
  • 时间复杂度 O(n)。
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
public class LeetCode_00890 {

    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> res = new ArrayList<>();
        for (String word : words) {
            if (match(word, pattern)) {
                res.add(word);
            }
        }
        return res;
    }

    private boolean match(String s, String p) {
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j) && p.charAt(i) != p.charAt(j)
                        || s.charAt(i) != s.charAt(j) && p.charAt(i) == p.charAt(j)) {
                    return false;
                }
            }
        }
        return true;
    }
}

方法二：

  • 创建两个索引数组，用来记录字符出现的下标。
  • 下标范围为 [1, length]，若为 0 表示对应字符尚未出现过。
  • 同时遍历两个数组，两个索引数组中对应元素必须相同（有两种情况）。如果不同，说明不匹配。
  • 同时为 0 表示都是第一次出现。
  • 同时为 [1, length] 中的同一个值，表示之前该字符出现过。
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
public class LeetCode_00890 {

    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> res = new ArrayList<>();
        for (String word : words) {
            if (match(word, pattern)) {
                res.add(word);
            }
        }
        return res;
    }

    private boolean match(String s, String p) {
        // 两个数组记录字符出现位置，为 0 表示未出现过
        int[] index1 = new int[26];
        int[] index2 = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            int i1 = s.charAt(i) - 'a';
            int i2 = p.charAt(i) - 'a';
            // 不同表示不匹配
            if (index1[i1] != index2[i2]) {
                return false;
            }
            // 记录字符出现位置，注意取值为 [1, length]，因为 0 用来表示尚未出现过
            index1[i1] = index2[i2] = i + 1;
        }
        return true;
    }
}