Nerd For Tech
Published in

Nerd For Tech

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 <= 20
  • 1 <= words.length <= 50
  • words[i].length == pattern.length
  • pattern and words[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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store