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

example

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;
	}
}