Find and Replace Pattern
Swift + Pattern Matching = 🧠🛠️🚀
Check out the full story on The Swift Nerd blog with the link above.
Problem Description
Given a list of strings words and a string pattern, return a list of words[i] that match pattern. You may return the answer in any order.
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.
Examples
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.Input: words = ["a","b","c"], pattern = "a"
Output: ["a","b","c"]
Constraints
1 <= pattern.length <= 201 <= words.length <= 50words[i].length == pattern.lengthpatternandwords[i]are lowercase English letters.
Solution
This might look like a version of Rabin Karp pattern matching, however it is used for matching the absolute patterns. What we can think of is creating a bi-directional mapping of every word character to pattern character and vice-versa. This way, we can check if any mapping is incorrect then we can safely say that the word is not following the pattern. To simply our code, we will extract the logic into a helper function for checking if a word matches the pattern. We will iterate over the words and test our eligibility for every word, in the end filtering the list of words who passed the test. To match bi-directional mapping , we will create two [Character:Character] dictionaries and check the result. We also used the zip(_ , _) functional to pair-wise compare the characters in word and pattern.
Complexity Analysis
- Time Complexity: O(N * K), where N is the number of words, and K is the length of each word.
- Space Complexity: O(N * K), the space used by the answer.
Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!
You can find me on TheSwiftNerd | LinkedIn | Github
