Pattern Matching
Solve a medium-level problem of matching patterns in input strings using tries.
Problem statement
A pattern will match a word if it can be made equal to the word by inserting zero or more lowercase English characters at any position in the pattern.
Given an array of input string words and a string pattern, return true or false for each word if they can be matched to the pattern or not.
Example 1
Sample input
pattern: "KT"words: ["KnowledgeTransfer", "KneeTest", "KnowledgeTrip", "KneeCap", "CropTop"]
Sample output
[true, true, true, false, false]
Explanation
"KnowledgeTransfer" can be generated like this "K" + "nowledge" + "T" + "ransfer"."KneeTest" can be generated like this "K" + "nee" + "T" + "est"."KnowledgeTrip" can be generated like this "K" + "nowledge" + "T" + "rip".
Example 2
Sample input
pattern: "KnTr"words: ["KnowledgeTransfer", "KneeTest", "KnowledgeTrip", "KneeCap", "CropTop"]
Sample output
[true, false, true, false, false]
Explanation
"KnowledgeTransfer" can be generated like this "Kn" + "owledge" + "Tr" + "ansfer"."KnowledgeTrip" can be generated like this "Kn" + "owledge" + "Tr" + "ip".
Example 3
Sample input
pattern: "CT"words: ["KnowledgeTransfer", "KneeTest", "KnowledgeTrip", "KneeCap", "CropTop"]
Sample output
[false, false , false, false, true]
Explanation
"CropTop" can be generated like this "C" + "rop" + "T" + "op".
Try it yourself
Please try to solve the problem yourself before reading the solution.
#include <iostream>#include <vector>using namespace std;vector<bool> patternMatcher(vector<string>& words, string pattern) {// your code goes herevector<bool> ans;return ans;}
Intuition
Let's discuss the critical observations over here. First, the uppercase letters must be in the same order in the pattern as they appear in the word. The lowercase letters might or might not be part of the pattern. This problem deals with pattern matching in strings. Tries can be an ideal candidate for solving this.
There are both uppercase and lowercase letters; therefore, an array of size 52 is used to store the child trie nodes. We store lowercase letters in the first 26 indices and uppercase letters in the last 26 indices. We ...