Leetcode Daily Problem - [890] Find and Replace Pattern

Problem Statement

Given a list of strings words and a string pattern, return a list of words[i] that match the 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.

In simple language problem is only that if there are two strings word and pattern then :

if all the characters of word are mapped to only one character of pattern

and if all the characters of pattern are mapped to only one character of word
then word will be added to the answer array.

Mapping should be done in respective order only.

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

Explanation :

Given that pattern is abb, it has two characters a and b.
Now we check with all the wordStrings in the words array.
We will store all the wordStrings in a newArray if the characters of the pattern are mapped with respective unique characters of the word.
After checking all the wordStrings in the given words array, the strings that fulfill the above condition are mee, aqq, and ccc because in these strings a and b of the pattern are mapped with only one character of the string.
Now those strings in newArray that satisfy the second condition will be added to the answerArray.
The second condition is the same as the first condition but this time characters of strings in newArray should be mapped with only one character of pattern.
After checking all the strings in newArray, the strings that fulfill the second condition too are - mee and aqq. [ ccc is eliminated because c will be mapped with a and b both ]

Hence, answer is [ "mee", "aqq" ]

Solution Writing

Appraoch 1

 /* This approach is same as what we discussed above in explanation */
 vector<string> findAndReplacePattern(vector<string>& words, string pattern) {    
        vector<string> newArray;
        for(auto &word:words){
            unordered_map<char,char> patternToWord;
            bool add=true;
            for(int i=0;i<pattern.length();i++){
                if(patternToWord.find(pattern[i])!=patternToWord.end()){
                    if(patternToWord[pattern[i]]!=word[i]){
                        add=false;
                        break;
                    }
                }else{
                    patternToWord[pattern[i]]=word[i];
                }
            }

            if(add){
                newArray.push_back(word);
            }
        }
        // here newArray will be [ 'mee', 'aqq', 'ccc' ] as explained above
        vector<string> ans;

        for(auto &word:newArray){
            unordered_map<char,char> wordToPattern;
            bool add=true;
            for(int i=0;i<pattern.length();i++){
                if(wordToPattern.find(word[i])!=wordToPattern.end()){
                    if(wordToPattern[word[i]]!=pattern[i]){
                        add=false;
                        break;
                    }
                }else{
                    wordToPattern[word[i]]=pattern[i];
                }
            }

            if(add){
                ans.push_back(word);
            }
        }

        return ans;
    }

Approach -2

Approach 2 is nothing but a slight optimization in above code.
We can use only one loop for performing same task using two maps.

vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> ans;
        for(auto &word:words){
            unordered_map<char,char> patternToWord;
            unordered_map<char,char> wordToPattern;
            bool addToAnswer=true;
            for(int i=0;i<pattern.length();i++){
                if(patternToWord.find(pattern[i])!=patternToWord.end()){
                    if(patternToWord[pattern[i]]!=word[i]){
                        addToAnswer=false;
                        break;
                    }
                }else{
                    if(wordToPattern.find(word[i])!=wordToPattern.end()){
                        if(wordToPattern[word[i]]!=pattern[i]){
                            addToAnswer=false;
                            break;
                        }
                    }
                    patternToWord[pattern[i]]=word[i];
                    wordToPattern[word[i]]=pattern[i];
                }
            }

            if(addToAnswer){
                ans.push_back(word);
            }
        }
        return ans;
    }

That's all about this problem.

As a problem setter I can add some more conditions to this problem to make a new problem :

Give some characters the ability to get mapped with 2 or more characters.
If k characters of either pattern or word can be replaced with any character then what would be the maximum number of words possible or which words will be in the answer array?
More such conditions can be added and this problem can become more interesting.

Thank you for reading!!

Leetcode Daily Problem - [890] Find and Replace Pattern

Table of contents

Problem Statement

Solution Writing