Skip to content

1258. Synonymous Sentences

  • Time: $O(2^n)$
  • Space: $O(2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
 public:
  vector<string> generateSentences(vector<vector<string>>& synonyms,
                                   string text) {
    set<string> ans;
    unordered_map<string, vector<string>> graph;
    queue<string> q{{text}};

    for (const vector<string>& synonym : synonyms) {
      const string& s = synonym[0];
      const string& t = synonym[1];
      graph[s].push_back(t);
      graph[t].push_back(s);
    }

    while (!q.empty()) {
      const string u = q.front();
      q.pop();
      ans.insert(u);
      vector<string> words = split(u);
      for (string& word : words) {
        const auto it = graph.find(word);
        if (it == graph.cend())
          continue;
        for (const string& synonym : it->second) {
          // Replace words[i] with its synonym.
          word = synonym;
          const string newText = join(words, ' ');
          if (!ans.count(newText))
            q.push(newText);
        }
      }
    }

    return {ans.begin(), ans.end()};
  }

 private:
  vector<string> split(const string& s) {
    vector<string> words;
    istringstream iss(s);
    for (string token; iss >> token;)
      words.push_back(token);
    return words;
  }

  string join(const vector<string>& words, char c) {
    string joined;
    for (int i = 0; i < words.size(); ++i) {
      joined += words[i];
      if (i != words.size() - 1)
        joined += c;
    }
    return joined;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public List<String> generateSentences(List<List<String>> synonyms, String text) {
    Set<String> ans = new TreeSet<>();
    Map<String, List<String>> graph = new HashMap<>();
    Queue<String> q = new ArrayDeque<>(Arrays.asList(text));

    for (List<String> synonym : synonyms) {
      final String s = synonym.get(0);
      final String t = synonym.get(1);
      graph.putIfAbsent(s, new ArrayList<>());
      graph.putIfAbsent(t, new ArrayList<>());
      graph.get(s).add(t);
      graph.get(t).add(s);
    }

    while (!q.isEmpty()) {
      final String u = q.poll();
      ans.add(u);
      String[] words = u.split("\\s");
      for (int i = 0; i < words.length; ++i)
        for (final String synonym : graph.getOrDefault(words[i], new ArrayList<>())) {
          // Replace words[i] with its synonym.
          words[i] = synonym;
          final String newText = String.join(" ", words);
          if (!ans.contains(newText))
            q.offer(newText);
        }
    }

    return new ArrayList<>(ans);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from sortedcontainers import SortedSet


class Solution:
  def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
    ans = SortedSet()
    graph = collections.defaultdict(list)
    q = collections.deque([text])

    for s, t in synonyms:
      graph[s].append(t)
      graph[t].append(s)

    while q:
      u = q.popleft()
      ans.add(u)
      words = u.split()
      for i, word in enumerate(words):
        for synonym in graph[word]:
          # Replace words[i] with its synonym.
          words[i] = synonym
          newText = ' '.join(words)
          if newText not in ans:
            q.append(newText)

    return list(ans)