890. Find and Replace Pattern

[TODO] Version #4 Use 1 Map

二刷 07/2022

Version #3 2 Arrays as HashMaps

Time O(MN)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Find and Replace Pattern.

Memory Usage: 43 MB, less than 57.14% of Java online submissions for Find and Replace Pattern.

class Solution {

    public List<String> findAndReplacePattern(String[] words, String pattern) {

        List<String> result = new ArrayList<>();

        for (String word : words) {

            if (isMatch(word, pattern)) {

                result.add(word);

            }

        }

        return result;

    }

    

    private boolean isMatch(String word, String pattern) {

        if (word.length() != pattern.length()) {

            return false;

        }

        char[] wordToPattern = new char[26];

        boolean[] usedPattern = new boolean[26];

        for (int i = 0; i < word.length(); i++) {

            char wc = word.charAt(i);

            char pc = pattern.charAt(i);

            if (wordToPattern[wc - 'a'] == 0) {

                if (usedPattern[pc - 'a']) {

                    return false;

                }

                wordToPattern[wc - 'a'] = pc;

                usedPattern[pc - 'a'] = true;

                continue;

            }

            if (wordToPattern[wc - 'a'] != pc) {

                return false;

            }

        }

        return true;

    }

}

一刷

Version #2 Counter
The mapping relationship is bi-direction so I have actually two maps


 100.00 %
class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> result = new ArrayList<>();
        char[] patternArray = pattern.toCharArray();
        for (String word : words) {
            if (isMatch(word.toCharArray(), patternArray)) {
                result.add(word);
            }
        }
        return result;
    }
   
    private boolean isMatch(char[] word, char[] pattern) {
        if (word.length != pattern.length) {
            return false;
        }
        char[] word2Pat = new char[256];
        char[] pat2Word = new char[256]; 
        for (int i = 0; i < word.length; i++) {
            if (word2Pat[word[i]] == 0) {
                if (pat2Word[pattern[i]] == 0) {
                    word2Pat[word[i]] = pattern[i];
                    pat2Word[pattern[i]] = word[i];
                } else {
                    return false;
                }
            } else if (word2Pat[word[i]] != pattern[i]) {
                return false;
            }
        }
        return true;
    }
}


Version #1 Normalize word
Use the index of first occurrence as id of the character
Kind of like hashing

Stream version
Beats 0%

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        if (words == null || words.length == 0 || pattern == null) {
            return null;
        }
        Integer[] target = normalize(pattern);
        return Arrays.stream(words)
            .filter(word -> Arrays.equals(normalize(word), target))
            .collect(Collectors.toList());
    }
    private Integer[] normalize(String word) {
        Map<Character, Integer> idMap = new HashMap<>();
        // Use the index of first occurance as id of the character
        return word.chars().mapToObj(i -> (char) i)
            .map(c -> {
                Integer id = idMap.get(c);
                if (id == null) {
                    id = idMap.size();
                    idMap.put(c, id);
                }
                return id;
            }).toArray(size -> new Integer[size]);
    }
}