Find all strings that match specific pattern in a dictionary - GeeksforGeeks

Find all strings that match specific pattern in a dictionary - GeeksforGeeks
Given a dictionary of words, find all strings that matches the given pattern where every character in the pattern is uniquely mapped to a character in the dictionary.

dict = ["abb", "abc", "xyz", "xyy"];
pattern = "foo"
Output: [xyy abb]
Explanation: 
xyy and abb have same character at index 1 and 2 like the pattern

The idea is to encode the pattern in such a way that any word from the dictionary that matches the pattern will have same hash as that of the pattern after encoding. We iterate through all words in dictionary one by one and print the words that have same hash as that of the pattern.

// Function to encode given string

string encodeString(string str)

{

    unordered_map<char, int> map;

    string res = "";

    int i = 0;

    // for each character in given string

    for (char ch : str)

    {

        // If the character is occurring for the first

        // time, assign next unique number to that char

        if (map.find(ch) == map.end())

            map[ch] = i++;

        // append the number associated with current

        // character into the output string

        res += to_string(map[ch]);

    }

    return res;

}

// Function to print all the strings that match the

// given pattern where every character in the pattern is

// uniquely mapped to a character in the dictionary

void findMatchedWords(unordered_set<string> dict,

                      string pattern)

{

    // len is length of the pattern

    int len = pattern.length();

    // encode the string

    string hash = encodeString(pattern);

    // for each word in the dictionary

    for (string word : dict)

    {

        // If size of pattern is same as size of current

        // dictionary word and both pattern and the word

        // has same hash, print the word

        if (word.length() == len && encodeString(word) == hash)

            cout << word << " " ;

    }

}

http://code.geeksforgeeks.org/zHMsNn
public static ArrayList<String> match(String[] dict,String pattern){
  ArrayList<String> retVal=new ArrayList<>();
  int[] rule=makePatternRules(pattern);
  for(int i=0;i<dict.length;i++){
    int[] arr=makePatternRules(dict[i]);
    if(Arrays.equals(arr, rule)){
      retVal.add(dict[i]);
    }
  }
  return retVal;
}
public static int[] makePatternRules(String pattern){
HashMap<Character,Integer> map=new HashMap<>();
int[] rule=new int[pattern.length()];
for(int i=0;i<pattern.length();i++){
  if(!map.containsKey(pattern.charAt(i))){
    map.put(pattern.charAt(i), i);
  }
  rule[i]=map.get(pattern.charAt(i));
}
return rule;
}
Read full article from Find all strings that match specific pattern in a dictionary - GeeksforGeeks