## Thursday, August 11, 2016

### 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)){
}
}
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;
}