Find and Replace Pattern (Leetcode 890)

Difficulty: Medium Link: Day 21: May Leetcode Challenge

Problem Description

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.

Examples

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.
Input: words = ["a","b","c"], pattern = "a"
Output: ["a","b","c"]

Constraints

  • 1 <= pattern.length <= 20
  • 1 <= words.length <= 50
  • words[i].length == pattern.length
  • pattern and words[i] are lowercase English letters.

Solution

This might look like a version of Rabin Karp pattern matching, however it is used for matching the absolute patterns. What we can think of is creating a bi-directional mapping of every word character to pattern character and vice-versa. This way, we can check if any mapping is incorrect then we can safely say that the word is not following the pattern. To simply our code, we will extract the logic into a helper function for checking if a word matches the pattern. We will iterate over the words and test our eligibility for every word, in the end filtering the list of words who passed the test. To match bi-directional mapping , we will create two [Character:Character] dictionaries and check the result. We also used the zip(_ , _) functional to pair-wise compare the characters in word and pattern.

Swift

class Solution {
func findAndReplacePattern(_ words: [String], _ pattern: String) -> [String] {
var output = [String]()
for word in words {
if isMatch(word,pattern) {
output.append(word)
}
}
return output
}
func isMatch(_ word:String, _ pattern:String) -> Bool {
var mapW = [Character:Character]()
var mapP = [Character:Character]()
for (w,p) in zip(word,pattern){
if mapW[w] == nil{
mapW[w] = p
}
if mapP[p] == nil{
mapP[p] = w
}
if mapW[w] != p || mapP[p] != w {
return false
}
}
return true
}
}

Python

class Solution(object):
def findAndReplacePattern(self, words, pattern):
def match(word):
m1, m2 = {}, {}
for w, p in zip(word, pattern):
if w not in m1: m1[w] = p
if p not in m2: m2[p] = w
if (m1[w], m2[p]) != (p, w):
return False
return True
return filter(match, words)
view raw find_and_replace.py hosted with ❤ by GitHub

Java

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;
}
public boolean match(String word, String pattern) {
Map<Character, Character> m1 = new HashMap();
Map<Character, Character> m2 = new HashMap();
for (int i = 0; i < word.length(); ++i) {
char w = word.charAt(i);
char p = pattern.charAt(i);
if (!m1.containsKey(w)) m1.put(w, p);
if (!m2.containsKey(p)) m2.put(p, w);
if (m1.get(w) != p || m2.get(p) != w)
return false;
}
return true;
}
}

Complexity Analysis

  • Time Complexity: O(N * K), where N is the number of words, and K is the length of each word.
  • Space Complexity: O(N * K), the space used by the answer.

Leave a Reply

Your email address will not be published. Required fields are marked *