Synonymous Sentences - Practice Coding Problems

Synonymous Sentences - Problem

Array Hash Table String Backtracking Sort Union Find Medium

You are given a list of equivalent string pairs synonyms where synonyms[i] = [s_i, t_i] indicates that s_i and t_i are equivalent strings. You are also given a sentence text.

Return all possible synonymous sentences sorted lexicographically.

A synonymous sentence is formed by replacing zero or more words in the original sentence with their synonyms.

Input & Output

Example 1 — Basic Synonyms

$ Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today"

› Output: ["I am cheerful today","I am happy today","I am joy today"]

💡 Note: The word 'happy' can be replaced with 'joy' or 'cheerful' (since happy↔joy↔cheerful are all connected). The other words remain unchanged.

Example 2 — Multiple Words with Synonyms

$ Input: synonyms = [["happy","joy"],["cheerful","content"]], text = "I am happy today"

› Output: ["I am happy today","I am joy today"]

💡 Note: Only 'happy' has synonyms in this case. The pairs [happy,joy] and [cheerful,content] are separate groups since they're not connected.

Example 3 — No Synonyms Found

$ Input: synonyms = [["a","b"],["c","d"]], text = "I like coding"

› Output: ["I like coding"]

💡 Note: None of the words in the sentence have synonyms in the given list, so only the original sentence is returned.

Constraints

0 ≤ synonyms.length ≤ 10
synonyms[i].length == 2
1 ≤ synonyms[i][j].length, text.length ≤ 10
synonyms[i][0] ≠ synonyms[i][1]
text consists of at most 10 words

Visualization

Tap to expand

Understanding the Visualization

Input

Synonym pairs and original sentence

Process

Find all words that can be replaced with synonyms

Output

All possible sentences sorted lexicographically

Key Takeaway

🎯 Key Insight: Group transitively connected synonyms, then generate all combinations systematically

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is to group all transitively connected synonyms using Union Find, then use backtracking to generate all possible sentence combinations. Best approach uses Union Find + Backtracking for efficient synonym grouping. Time: O(S×α(S) + k^n × L), Space: O(S + k^n × L)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Backtracking	O(k^n × L)	O(k^n × L)	Generate all possible combinations by trying every synonym for each word
Optimized Backtracking with Union Find	O(S×α(S) + k^n × L)	O(S + k^n × L)	Use Union Find to group all transitive synonyms, then generate combinations

Brute Force with Backtracking — Algorithm Steps

For each word, scan all synonym pairs to find alternatives
Recursively generate all combinations
Sort results lexicographically

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse Input

Split sentence into words and identify synonyms

Backtrack

For each word, try all possible synonyms recursively

Collect Results

Sort all generated sentences lexicographically

Code -

solution.c — C

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

#define MAX_WORDS 20
#define MAX_SYNONYMS 20
#define MAX_RESULTS 1000
#define MAX_LEN 100

char synonyms[MAX_SYNONYMS][2][MAX_LEN];
int synonymCount = 0;
char words[MAX_WORDS][MAX_LEN];
int wordCount = 0;
char results[MAX_RESULTS][MAX_LEN * MAX_WORDS];
int resultCount = 0;

void backtrack(int index, char current[][MAX_LEN], int currentCount) {
    if (index == wordCount) {
        char sentence[MAX_LEN * MAX_WORDS] = "";
        for (int i = 0; i < currentCount; i++) {
            if (i > 0) strcat(sentence, " ");
            strcat(sentence, current[i]);
        }
        
        // Check for duplicates
        for (int i = 0; i < resultCount; i++) {
            if (strcmp(results[i], sentence) == 0) return;
        }
        
        strcpy(results[resultCount++], sentence);
        return;
    }
    
    char wordSynonyms[MAX_SYNONYMS][MAX_LEN];
    int synonymsCount = 0;
    strcpy(wordSynonyms[synonymsCount++], words[index]);
    
    for (int i = 0; i < synonymCount; i++) {
        if (strcmp(synonyms[i][0], words[index]) == 0) {
            strcpy(wordSynonyms[synonymsCount++], synonyms[i][1]);
        } else if (strcmp(synonyms[i][1], words[index]) == 0) {
            strcpy(wordSynonyms[synonymsCount++], synonyms[i][0]);
        }
    }
    
    for (int i = 0; i < synonymsCount; i++) {
        strcpy(current[currentCount], wordSynonyms[i]);
        backtrack(index + 1, current, currentCount + 1);
    }
}

int compare(const void *a, const void *b) {
    return strcmp((char*)a, (char*)b);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple parsing for synonyms (assumes proper format)
    char *ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            if (*ptr == '"') ptr++;
            char *start = ptr;
            while (*ptr && *ptr != '"') ptr++;
            strncpy(synonyms[synonymCount][0], start, ptr - start);
            synonyms[synonymCount][0][ptr - start] = 0;
            
            ptr += 2; // skip ",
            if (*ptr == '"') ptr++;
            start = ptr;
            while (*ptr && *ptr != '"') ptr++;
            strncpy(synonyms[synonymCount][1], start, ptr - start);
            synonyms[synonymCount][1][ptr - start] = 0;
            synonymCount++;
        }
        ptr++;
    }
    
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    char *token = strtok(line, " ");
    while (token) {
        strcpy(words[wordCount++], token);
        token = strtok(NULL, " ");
    }
    
    char current[MAX_WORDS][MAX_LEN];
    backtrack(0, current, 0);
    
    qsort(results, resultCount, sizeof(results[0]), compare);
    
    printf("[");
    for (int i = 0; i < resultCount; i++) {
        if (i > 0) printf(",");
        printf("\"%s\"", results[i]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^n × L)

k synonyms per word, n words, L for string operations and sorting

✓ Linear Growth

Space Complexity

O(k^n × L)

Store all possible sentences, each of length L

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 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 with Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler