# Match Specific Pattern

Last updated: 6th Sep, 2020

### Problem Statment

Given a dictionary of words and a pattern. Every character in the pattern is uniquely mapped to a character in the dictionary. Find all such words in the dictionary that match the given pattern.

#### Input

The First line contains the number(N) of words in dictionary, following line contains N strings and last line contains the pattern.

#### Output

All strings (seperated by spaces) in dictionary that match the given pattern.

Example 1:

    Input:
    4
    abb abc xyz xyy
    foo
    Output:
    abb xyy

Explanation: xyy and abb have the same character at index 1 and 2 like the pattern.

### Naive Approach:

We will use hash map to map every character of pattern to its corresponding character in string.

- If the current character is not been mapped, then map it to its corresponding character in given string
- If the current character has been mapped before then check if the corresponding character is same with current corresponding value or not
- If there are no contradictions then add this word to the match string array

#### Pseudo Code

function findMatchedWords(givenDictionary, givenPattern) {

- Traverse the dictionary and for every string in dictionary:
  - Create a Character array of 128 and initialize all with NULL
  - IF length of string and pattern match then:
    - Check if the character has been mapped before
      - IF Yes:
        - Check if the corresponding character is same with the current one
      - IF No:
        - Map it to corresponding character
  - On each successful traversal add the word to the array to be returned
- Finally return the array of matched strings

}

##### C++ Function Implementation

    bool check(string pattern, string word)
    {
        if (pattern.length() != word.length())
            return false;

        char ch[128] = { 0 };

        int len = word.length();

        for (int i = 0; i < len; i++) {
            if (ch[pattern[i]] == 0)
                ch[pattern[i]] = word[i];
            else if (ch[pattern[i]] != word[i])
                return false;
        }

        return true;
    }

    vector<string> findMatchedWords2(vector<string> dict, string pattern)
    {
        vector<string> match;
        int len = pattern.length();

        for (int i = 0; i < dict.size();i++) {

    		if (check(pattern, dict[i])){
                match.push_back(dict[i]);
    		}

    	}
        return match;
    }

##### Program Code

    #include <bits/stdc++.h>
    using namespace std;

    //------------------METHOD 1-------------------------------------
    bool check(string pattern, string word)
    {
        if (pattern.length() != word.length())
            return false;

        char ch[128] = { 0 };

        int len = word.length();

        for (int i = 0; i < len; i++) {
            if (ch[pattern[i]] == 0)
                ch[pattern[i]] = word[i];
            else if (ch[pattern[i]] != word[i])
                return false;
        }

        return true;
    }

    vector<string> findMatchedWords2(vector<string> dict, string pattern)
    {
        vector<string> match;
        int len = pattern.length();

        for (int i = 0; i < dict.size();i++) {

    		if (check(pattern, dict[i])){
                match.push_back(dict[i]);
    		}

    	}
        return match;
    }
    //---------- METHOD 2---------------------------------
    // Mapping every letter to a distinct number and making hash for every string
    // and checking it with the hash of given pattern
    /*
    string encodeString(string str)
    {
        unordered_map<char, int> map;
        string res = "";
        int i = 0;

        for (char ch : str) {
            if (map.find(ch) == map.end())
                map[ch] = i++;

            res += to_string(map[ch]);
        }

        return res;
    }

    vector<string> findMatchedWords(vector<string> dict,string pattern)
    {
        vector<string> match;
        int len = pattern.length();
      	string hash = encodeString(pattern);

        for (int i = 0; i < dict.size();i++) {
            if (dict[i].length() == len && encodeString(dict[i]) == hash){
    			match.push_back(dict[i]);
    		}
        }
        return match;
    }
    */
    int main()
    {
    	int t;
    	cin >> t;
    	while(t--)
    	{
    		int n;
    		cin >> n;
    		vector<string> s(n);
    		for(int i = 0; i < n; i++)
    		    cin >> s[i];

    		string tt;
    		cin >> tt;

    		vector<string> res = findMatchedWords(s,tt);
            sort(res.begin(),res.end());
    		for(int i = 0; i < res.size(); i++)
    		    cout << res[i] << " ";
    		cout << endl;
    	}
    }