Formatted question description: https://leetcode.ca/all/890.html

890. Find and Replace Pattern (Medium)

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

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.)

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

You may return the answer in any order.

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.

Note:

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

Companies:
Google, Apple

Related Topics:
String

Solution 1.

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

    public boolean matchPattern(String word, String pattern) {
        if (word.length() != pattern.length())
            return false;
        Map<Character, Character> map1 = new HashMap<Character, Character>();
        Map<Character, Character> map2 = new HashMap<Character, Character>();
        int length = word.length();
        for (int i = 0; i < length; i++) {
            char c1 = word.charAt(i), c2 = pattern.charAt(i);
            if (map1.containsKey(c1)) {
                if (map1.get(c1) != c2)
                    return false;
            } else
                map1.put(c1, c2);
            if (map2.containsKey(c2)) {
                if (map2.get(c2) != c1)
                    return false;
            } else
                map2.put(c2, c1);
        }
        return true;
    }
}

############

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

    private boolean match(String s, String t) {
        int[] m1 = new int[128];
        int[] m2 = new int[128];
        for (int i = 0; i < s.length(); ++i) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            if (m1[c1] != m2[c2]) {
                return false;
            }
            m1[c1] = i + 1;
            m2[c2] = i + 1;
        }
        return true;
    }
}

// OJ: https://leetcode.com/problems/find-and-replace-pattern/
// Time: O(CW) where C is count of words and W is word length
// Space: O(W)
class Solution {
private:
    bool match(string &word, string &pattern) {
        unordered_map<char, char> m;
        unordered_set<char> used;
        for (int i = 0; i < word.size(); ++i) {
            if (m.find(word[i]) == m.end()) {
                if (used.find(pattern[i]) != used.end()) return false;
                m[word[i]] = pattern[i];
                used.insert(pattern[i]);                                            
            } else if (m[word[i]] != pattern[i]) return false;
        }
        return true;
    }
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> ans;
        for (auto word : words) {
            if (match(word, pattern)) ans.push_back(word);
        }
        return ans;
    }
};

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        def match(s, t):
            m1, m2 = [0] * 128, [0] * 128
            for i, (a, b) in enumerate(zip(s, t), 1):
                if m1[ord(a)] != m2[ord(b)]:
                    return False
                m1[ord(a)] = m2[ord(b)] = i
            return True

        return [word for word in words if match(word, pattern)]

############

class Solution(object):
    def findAndReplacePattern(self, words, pattern):
        """
        :type words: List[str]
        :type pattern: str
        :rtype: List[str]
        """
        ans = []
        set_p = set(pattern)
        for word in words:
            if len(set(word)) != len(set_p):
                continue
            fx = dict()
            equal = True
            for i, w in enumerate(word):
                if w in fx:
                    if fx[w] != pattern[i]:
                        equal = False
                        break
                fx[w] = pattern[i]
            if equal:
                ans.append(word)
        return ans

func findAndReplacePattern(words []string, pattern string) []string {
	match := func(s, t string) bool {
		m1, m2 := make([]int, 128), make([]int, 128)
		for i := 0; i < len(s); i++ {
			if m1[s[i]] != m2[t[i]] {
				return false
			}
			m1[s[i]] = i + 1
			m2[t[i]] = i + 1
		}
		return true
	}
	var ans []string
	for _, word := range words {
		if match(word, pattern) {
			ans = append(ans, word)
		}
	}
	return ans
}

function findAndReplacePattern(words: string[], pattern: string): string[] {
    return words.filter(word => {
        const map1 = new Map<string, number>();
        const map2 = new Map<string, number>();
        for (let i = 0; i < word.length; i++) {
            if (map1.get(word[i]) !== map2.get(pattern[i])) {
                return false;
            }
            map1.set(word[i], i);
            map2.set(pattern[i], i);
        }
        return true;
    });
}

use std::collections::HashMap;
impl Solution {
    pub fn find_and_replace_pattern(words: Vec<String>, pattern: String) -> Vec<String> {
        let pattern = pattern.as_bytes();
        let n = pattern.len();
        words
            .into_iter()
            .filter(|word| {
                let word = word.as_bytes();
                let mut map1 = HashMap::new();
                let mut map2 = HashMap::new();
                for i in 0..n {
                    if map1.get(&word[i]).unwrap_or(&n) != map2.get(&pattern[i]).unwrap_or(&n) {
                        return false;
                    }
                    map1.insert(word[i], i);
                    map2.insert(pattern[i], i);
                }
                true
            })
            .collect()
    }
}

890 - Find and Replace Pattern

890. Find and Replace Pattern (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

890. Find and Replace Pattern (Medium)

Solution 1.

All Problems

All Solutions