Created
February 12, 2019 19:04
-
-
Save Smakar20/6f35a72c3f6e59950269b3f915fa6c40 to your computer and use it in GitHub Desktop.
findAndReplacePattern.js created by smakar20 - https://repl.it/@smakar20/findAndReplacePatternjs
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
You have a list of words and a pattern, and you want to know which words in words matches the pattern. | |
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.) | |
Return a list of the words in words that match the given pattern. | |
You may return the answer in any order. | |
Example 1: | |
Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb" | |
Output: ["mee","aqq"] | |
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. | |
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation, | |
since a and b map to the same letter. | |
Note: | |
1 <= words.length <= 50 | |
1 <= pattern.length = words[i].length <= 20 | |
*/ | |
var findAndReplacePattern = function(words, pattern) { | |
var output = []; | |
var patternSetSize = (new Set(pattern.split(''))).size; | |
for (var word of words){ | |
if ((word.length !== pattern.length) || ((new Set(word.split(''))).size !== patternSetSize)) continue; | |
var wordObj = {}; | |
var count = 0; | |
for (var i = 0; i < word.length; i++){ | |
if(wordObj[word[i]] !== undefined && wordObj[word[i]] !== pattern[i]) break; | |
wordObj[word[i]] = pattern[i]; | |
count++; | |
} | |
if (count === pattern.length) output.push(word); | |
} | |
return output; | |
}; | |
findAndReplacePattern(["abc","deq","mee","aqq","dkd","ccc", "inn"], "abb"); | |
// Output: ["mee","aqq", "inn"] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment