890. Find and Replace Pattern
Approach
Check isomorphism via bidirectional character mapping; both word→pattern and pattern→word mappings must be consistent.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
// Approach: Check isomorphism via bidirectional character mapping; both word→pattern and pattern→word mappings must be consistent.
// Time: O(n · m) Space: O(n · m)
public class Solution
{
public IList<string> FindAndReplacePattern(string[] words, string pattern)
{
IList<string> ans = new List<string>();
foreach (string word in words)
{
if (IsIsomorphic(word, pattern))
ans.Add(word);
}
return ans;
}
private bool IsIsomorphic(string w, string p)
{
int[] wordMap = new int[128];
int[] patternMap = new int[128];
for (int i = 0; i < w.Length; i++)
{
if (wordMap[w[i]] != patternMap[p[i]])
return false;
wordMap[w[i]] = i + 1;
patternMap[p[i]] = i + 1;
}
return true;
}
}