How to solve LeetCode 1258 (Synonymous Sentences)?

This page provides optimized solutions for LeetCode problem 1258 (Synonymous Sentences) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test and refine your code.

LeetCode 1258: Synonymous Sentences Solution

LeetCode 1258 Solution Explanation

Explanation:

To solve this problem, we can use the concept of backtracking along with a depth-first search (DFS) approach. We will build a graph representing the synonyms relationships given in the input. Then, we can use backtracking to generate all possible sentences by replacing words with their synonyms.

Algorithm:

Build a graph where each word is a node and the synonyms relationships are edges.
Perform a Depth First Search (DFS) backtracking on the graph to generate all possible sentences by replacing words with their synonyms.
Keep track of the current sentence being built.
When we reach a word that has no synonyms (i.e., not present in the graph), add the current sentence to the result.
Continue the backtracking process until all words are processed.

Time Complexity:

The time complexity of this approach is O(n * s), where n is the number of words in the input sentence and s is the average number of synonyms for each word.

Space Complexity:

The space complexity is O(n), where n is the number of words in the input sentence.

: :

LeetCode 1258 Solutions in Java, C++, Python

import java.util.*;

class Solution {
    public List<String> generateSentences(List<List<String>> synonyms, String text) {
        Map<String, List<String>> graph = new HashMap<>();
        for (List<String> synonymPair : synonyms) {
            String word1 = synonymPair.get(0);
            String word2 = synonymPair.get(1);
            graph.computeIfAbsent(word1, k -> new ArrayList<>()).add(word2);
            graph.computeIfAbsent(word2, k -> new ArrayList<>()).add(word1);
        }
        
        List<String> result = new ArrayList<>();
        dfs(graph, text.split(" "), 0, new StringBuilder(), result);
        Collections.sort(result);
        return result;
    }
    
    private void dfs(Map<String, List<String>> graph, String[] words, int index, StringBuilder current, List<String> result) {
        if (index == words.length) {
            result.add(current.toString().trim());
            return;
        }
        
        String word = words[index];
        if (!graph.containsKey(word)) {
            dfs(graph, words, index + 1, current.append(word).append(" "), result);
            current.setLength(current.length() - word.length() - 1);
        } else {
            for (String synonym : graph.get(word)) {
                dfs(graph, words, index + 1, current.append(synonym).append(" "), result);
                current.setLength(current.length() - synonym.length() - 1);
            }
        }
    }
}

Interactive Code Editor for LeetCode 1258

Improve Your LeetCode 1258 Solution

Use the editor below to refine the provided solution for LeetCode 1258. Select a programming language and try the following:

Add import statements if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Loading editor...