890. Find and Replace Pattern

Question

Given a list of strings words and a string pattern, return a list of words[i] that match pattern. You may return the answer in any order.

A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.

Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.

Solution

遍历words，对pattern和words中的字符建立映射。
used[]数组记录访问状况。

如未建立映射关系，且word中的字符已建立映射，则不在结果中添加当前字符串。
如未建立映射，则建立新的word与pattern的映射关系。
如果当前已经建立映射，但是当前字符违反了映射关系，则不在结果中添加当前字符串。

Code

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> ret = new ArrayList<>();
        for(String word : words){
            HashMap<Character, Character> map = new HashMap<>();    //map characters from pattern and words
            boolean isSamePattern = true;
            int[] used = new int[26];
            
            for(int i = 0; i < word.length(); i++){
                char pc = pattern.charAt(i), wc = word.charAt(i);
                if( !map.containsKey(pc) ){
                    if(used[wc-'a'] == 0){  //add new map if there is no map between characters and the character in word is not used
                        map.put( pc, wc );
                        used[wc-'a']++;
                    }
                    else{
                        isSamePattern = false;
                        break;
                    }
                }
                else if( map.get(pc) != wc ){   //drop the word if not follow the pattern
                    isSamePattern = false;
                    break;
                }
            }
            if(isSamePattern) ret.add(word);
        }
        return ret;
    }
}