Find and Replace Pattern - Practice Coding Problems

Find and Replace Pattern - Problem

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.

Input & Output

Example 1 — Basic Pattern Matching

$ Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"

› Output: ["mee","aqq"]

💡 Note: "mee" matches pattern "abb" (m→a, e→b), and "aqq" matches (a→a, q→b). Both have the same structure where first char differs from second and third chars which are same.

Example 2 — No Matches

$ Input: words = ["a","b","c"], pattern = "aa"

› Output: []

💡 Note: No single character word can match pattern "aa" which requires two identical characters.

Example 3 — All Different Pattern

$ Input: words = ["abc","cab","xyz"], pattern = "abc"

› Output: ["abc","cab","xyz"]

💡 Note: Pattern "abc" means all characters different. All three words have distinct characters so they all match.

Constraints

1 ≤ words.length ≤ 50
1 ≤ pattern.length ≤ 20
1 ≤ words[i].length ≤ 20
words[i] and pattern consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Words list and pattern to match against

Process

Check each word for bijective character mapping

Output

List of words that match the pattern

Key Takeaway

🎯 Key Insight: Use bidirectional hash maps to ensure bijective character mapping between pattern and word

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that we need bijective mapping - each pattern character maps to exactly one word character and vice versa. Best approach uses bidirectional hash maps to verify both directions simultaneously. Time: O(n × m), Space: O(k) where k is unique characters.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Character Mapping	O(n × m)	O(k)	For each word, try to build a mapping from pattern to word characters
Hash Map Normalization	O(n × m)	O(m)	Normalize both pattern and words to a canonical form for comparison

Brute Force Character Mapping — Algorithm Steps

For each word, create empty mappings
For each character position, check if mapping is consistent
Add word to result if all characters map correctly

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Word

For each word, try to build consistent mapping

Map Characters

Create pattern→word and word→pattern mappings

Verify

Check if both mappings are consistent throughout

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool matches(char* word, char* pattern) {
    int len = strlen(word);
    if (len != strlen(pattern)) {
        return false;
    }
    
    char pToW[256];
    char wToP[256];
    bool pUsed[256] = {false};
    bool wUsed[256] = {false};
    
    for (int i = 0; i < len; i++) {
        char pChar = pattern[i];
        char wChar = word[i];
        
        if (pUsed[pChar]) {
            if (pToW[pChar] != wChar) {
                return false;
            }
        } else {
            pToW[pChar] = wChar;
            pUsed[pChar] = true;
        }
        
        if (wUsed[wChar]) {
            if (wToP[wChar] != pChar) {
                return false;
            }
        } else {
            wToP[wChar] = pChar;
            wUsed[wChar] = true;
        }
    }
    
    return true;
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    input[strcspn(input, "\n")] = 0;
    
    char words[100][100];
    int wordCount = 0;
    
    char* token = strtok(input + 1, ",");
    while (token != NULL) {
        while (*token == ' ' || *token == '"') token++;
        int len = strlen(token);
        while (len > 0 && (token[len-1] == ' ' || token[len-1] == '"' || token[len-1] == ']')) {
            token[len-1] = '\0';
            len--;
        }
        strcpy(words[wordCount++], token);
        token = strtok(NULL, ",");
    }
    
    char pattern[100];
    fgets(pattern, sizeof(pattern), stdin);
    pattern[strcspn(pattern, "\n")] = 0;
    
    printf("[");
    bool first = true;
    for (int i = 0; i < wordCount; i++) {
        if (matches(words[i], pattern)) {
            if (!first) printf(",");
            printf("\"%s\"", words[i]);
            first = false;
        }
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

For each of n words, we check m characters in the pattern

✓ Linear Growth

Space Complexity

O(k)

Hash map stores at most k unique characters from pattern/word

✓ Linear Space

89.2K Views

Medium Frequency

~15 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Character Mapping — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler