Let's make this one less mysterious. For 890. Find and Replace Pattern, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: straightforward implementation.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are findAndReplacePattern.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02You have a list of words and a pattern, and you want to know which words in words matches the pattern.
03
04A 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.
05
06(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.)
07
08Return a list of the words in words that match the given pattern.
09
10You may return the answer in any order.
11
12
13
14Example 1:
15
16Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
17Output: ["mee","aqq"]
18Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}.
19"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation,
20since a and b map to the same letter.
21
22
23Note:
24
251 <= words.length <= 50
261 <= pattern.length = words[i].length <= 20
27**/
28
29/**
30Solution
31Approach 1: Two Maps
32Intuition and Algorithm
33
34If say, the first letter of the pattern is "a", and the first letter of the word is "x", then in the permutation, "a" must map to "x".
35
36We can write this bijection using two maps: a forward map m1 and a backwards map m2.
37
38m1:"a"→"x"
39
40m2:"x"→"a"
41
42Then, if there is a contradiction later, we can catch it via one of the two maps.
43For example, if the (word, pattern) is ("aa", "xy"), we will catch the mistake in m1 (namely, m1("a")="x"="y").
44Similarly, with (word, pattern) = ("ab", "xx"), we will catch the mistake in m2.
45
46//Java
47/**
48class Solution {
49 public List<String> findAndReplacePattern(String[] words, String pattern) {
50 List<String> ans = new ArrayList();
51 for (String word: words)
52 if (match(word, pattern))
53 ans.add(word);
54 return ans;
55 }
56
57 public boolean match(String word, String pattern) {
58 Map<Character, Character> m1 = new HashMap();
59 Map<Character, Character> m2 = new HashMap();
60
61 for (int i = 0; i < word.length(); ++i) {
62 char w = word.charAt(i);
63 char p = pattern.charAt(i);
64 if (!m1.containsKey(w)) m1.put(w, p);
65 if (!m2.containsKey(p)) m2.put(p, w);
66 if (m1.get(w) != p || m2.get(p) != w)
67 return false;
68 }
69
70 return true;
71 }
72}
73
74Complexity Analysis
75
76Time Complexity: O(N∗K), where N is the number of words, and KK is the length of each word.
77
78Space Complexity: O(N∗K), the space used by the answer.
79**/
80
81/**
82Approach 2: One Map
83Intuition and Algorithm
84
85As in Approach 1, we can have some forward map \text{m1} : \mathbb{L} \rightarrow \mathbb{L}m1:L→L, where \mathbb{L}L is the set of letters.
86
87However, instead of keeping track of the reverse map \text{m2}m2, we could simply make sure that every value \text{m1}(x)m1(x) in the codomain is reached at most once. This would guarantee the desired permutation exists.
88
89So our algorithm is this: after defining \text{m1}(x)m1(x) in the same way as Approach 1 (the forward map of the permutation), afterwards we make sure it reaches distinct values.
90
91//Java
92class Solution {
93 public List<String> findAndReplacePattern(String[] words, String pattern) {
94 List<String> ans = new ArrayList();
95 for (String word: words)
96 if (match(word, pattern))
97 ans.add(word);
98 return ans;
99 }
100
101 public boolean match(String word, String pattern) {
102 Map<Character, Character> M = new HashMap();
103 for (int i = 0; i < word.length(); ++i) {
104 char w = word.charAt(i);
105 char p = pattern.charAt(i);
106 if (!M.containsKey(w)) M.put(w, p);
107 if (M.get(w) != p) return false;
108 }
109
110 boolean[] seen = new boolean[26];
111 for (char p: M.values()) {
112 if (seen[p - 'a']) return false;
113 seen[p - 'a'] = true;
114 }
115 return true;
116 }
117}
118
119Complexity Analysis
120
121Time Complexity: O(N∗K), where N is the number of words, and KK is the length of each word.
122
123Space Complexity: O(N∗K), the space used by the answer.
124**/
125
126/**
127//Your runtime beats 59.66 % of cpp submissions.
128class Solution {
129public:
130 vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
131 vector<string> remain_words;
132 for(int i = 0; i < words.size(); i++){
133 map<char, char> pt2word;
134 map<char, char> word2pt;
135 bool match = true;
136 for(int j = 0; j < words[i].size(); j++){
137 if(pt2word.find(pattern[j])==pt2word.end()){ //not in map
138 pt2word.insert(make_pair(pattern[j], words[i][j]));
139 }else if(words[i][j] != pt2word[pattern[j]]){
140 cout << words[i][j] << pattern[j] << (words[i][j] != pt2word[pattern[j]]) << endl;
141 match = false;
142 break;
143 }
144
145 if(word2pt.find(words[i][j])==word2pt.end()){ //not in map
146 word2pt.insert(make_pair(words[i][j], pattern[j]));
147 }else if(pattern[j] != word2pt[words[i][j]]){
148 cout << words[i][j] << pattern[j] << (pattern[j] != word2pt[words[i][j]]) << endl;
149 match = false;
150 break;
151 }
152 }
153 if(match){
154 remain_words.push_back(words[i]);
155 }
156 }
157 return remain_words;
158 }
159};
160**/
161
162//Your runtime beats 100.00 % of cpp submissions.
163class Solution {
164public:
165 vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
166 vector<string> remain_words;
167 for(int i = 0; i < words.size(); i++){
168 map<char, char> pt2word;
169 map<char, char> word2pt;
170 bool match = true;
171 for(int j = 0; j < words[i].size(); j++){
172 if(pt2word.find(pattern[j])==pt2word.end()){ //not in map
173 pt2word.insert(make_pair(pattern[j], words[i][j]));
174 }
175 if(word2pt.find(words[i][j])==word2pt.end()){ //not in map
176 word2pt.insert(make_pair(words[i][j], pattern[j]));
177 }
178 if((words[i][j] != pt2word[pattern[j]]) || (pattern[j] != word2pt[words[i][j]])){
179 match = false;
180 break;
181 }
182 }
183 if(match){
184 remain_words.push_back(words[i]);
185 }
186 }
187 return remain_words;
188 }
189};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.