leetcode - [890] Find and Replace Pattern

2020/06/27

问题描述

You have a list of words and a pattern, and you want to know which words in words matches the pattern.

Return a list of the words in words that match the given pattern.

You may return the answer in any order.

words字符串列表中找出与pattern相同模式的字符串。

举个例子:

Example 1:
Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. 
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation,
since a and b map to the same letter.

解法1

Thanks @caraxin

先来看下示意图:

首先,遍历words字符串列表,依次与pattern进行比较。

那么具体如何比较?

第一步,创建两个临时数组,分别记录对应字母出现的频率。

第二步,分别遍历两个字符串:

if (wi[w.charAt(i) - 'A'] != pi[p.charAt(i) - 'A']){
    return false;
} else {
    wi[w.charAt(i) - 'A'] = pi[p.charAt(i) - 'A'] = i + 1;
}

这里非常巧妙。

看上图中左边的那个例子,遍历到最后一个字母时,分别是ch

由于,这两个字母对应数组中的值都是初始值,也就是0,所以符合模式。

再来看上图右边的例子,遍历到第三个字母时,分别是ah

wi对应a的值已经是2了,但是pi对应h的值为0,所以模式不匹配。

来看下完整实现:

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        
        List<String> ans = new LinkedList<>();
        
        for (String w: words){
            if (match(w, pattern)){
                ans.add(w);
            }
        }
        return ans;
    }
    
    private boolean match(String w, String p){
        
        int[] wi = new int[256];
        int[] pi = new int[256];
        int minLen = Math.min(w.length(), p.length());
        
        for (int i = 0; i < minLen; i++){
            if (wi[w.charAt(i) - 'A'] != pi[p.charAt(i) - 'A']){
                return false;
            } else {
                wi[w.charAt(i) - 'A'] = pi[p.charAt(i) - 'A'] = i + 1;
            }
        }
        return true;
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory