[leetcode/lintcode 题解] 算法面试高频题详解:查找和替换模式-阿里云开发者社区

开发者社区> 算法编程> 正文
登录阅读全文

[leetcode/lintcode 题解] 算法面试高频题详解:查找和替换模式

简介: [leetcode/lintcode 题解] 算法面试高频题详解:查找和替换模式

描述
你有一个单词列表 words 和一个模式 pattern,你想知道 words 中的哪些单词与模式匹配。
如果存在字母的排列 p ,使得将模式中的每个字母 x 替换为 p(x) 之后,我们就得到了所需的单词,那么单词与模式是匹配的。
(回想一下,字母的排列是从字母到字母的双射:每个字母映射到另一个字母,没有两个字母映射到同一个字母。)
返回 words 中与给定模式匹配的单词列表。
你可以按任何顺序返回答案。

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

在线评测地址:领扣题库官网

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

解题思路
遍历words,逐个匹配是否满足pattern,在匹配时,借助HashMap建立字符映射关系,条件是:每个字母映射到另一个字母中,没有两个字母映射到同一个字母。
源代码

public class Solution {
    /**
     * @param words: word list
     * @param pattern: pattern string
     * @return: list of matching words
     */
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        // Write your code here.
        int[] p = F(pattern);
        List<String> res = new ArrayList<String>();
        for (String w : words)
            if (Arrays.equals(F(w), p)) res.add(w);
        return res;
    }

    public int[] F(String w) {
        HashMap<Character, Integer> m = new HashMap<>();
        int n = w.length();
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            m.putIfAbsent(w.charAt(i), m.size());
            res[i] = m.get(w.charAt(i));
        }
        return res;
    }
}

更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: