Similar Problems

Similar Problems not available

String Matching In An Array - Leetcode Solution

Companies:

LeetCode:  String Matching In An Array Leetcode Solution

Difficulty: Easy

Topics: string array  

Problem Statement:

Given an array 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.

Example:

Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb" Output: ["mee","aqq"]

Explanation:

"mee" matches the pattern because there is a bijection between letters "a" and "m", and between letters "b" and "e".

"aqq" matches the pattern because there is a bijection between letters "a" and "a", and between letters "b" and "q".

Both abc and dkd do not match the pattern.

Solution:

The problem requires to check which words from the given list of words matches the given pattern. To solve the problem, we can check for each word from the given words list whether it satisfies the given pattern or not.

For each word from the list, we will use a dictionary to store the mapping between the given pattern and the corresponding letters in the word. We will iterate through the characters of the word and the pattern and if we find a new mapping, we will add it to the dictionary.

However, if we have already established a mapping from the pattern characters to the word characters and we come across a character in the pattern that is already mapped to a different character in the given word, we will return False. If the matching condition keeps on satisfying for all the words, then we will append the word to our resultant array.

The final solution will look like this:

def findAndReplacePattern(words, pattern):

res = []

for w in words:
    p2w, w2p = {}, {}
    for p, c in zip(pattern, w):
        if p not in p2w:
            p2w[p] = c
        if c not in w2p:
            w2p[c] = p
        if (p2w[p], w2p[c]) != (c, p):  # If doesn't match then don't add it
            break
    else:
        res.append(w)
return res

words = ["abc","deq","mee","aqq","dkd","ccc"] pattern = "abb" print(findAndReplacePattern(words, pattern))

Output: ["mee", "aqq"]

String Matching In An Array Solution Code

1