【LeetCode（Java） - 1258】近义词句子

1、题目描述

2、解题思路

??使用并查集集中管理所有的同义词，然后使用一个 HashMap 存储近义词集合，key 为并查集的 parent，value 为并查集 parent 对应的集合。

??对 text 每一个单词进行深度优先搜索：

??1、判断当前单词是否有同义词，如果有，则当前单词替换为所有的可能的近义词；

??2、接着对下一个单词进行 DFS。

??中间涉及大量的字符串拼接，不要直接用加号，而是使用 StringBuilder 来进行拼接，需要注意的是，需要进行同义词替换时，要新建一个 StringBuilder 继续往下深入，而不是一个 StringBuilder 用到底。

3、解题代码

class Solution {
    private Word word;private Map<String, HashSet<String>> dic = new HashMap<>();public List<String> generateSentences(List<List<String>> synonyms, String text) {
    List<String> ans = new ArrayList<>();if (text == null || text.length() == 0) {
    return ans;}if (synonyms == null || synonyms.size() == 0) {
    ans.add(text);return ans;}word = new Word(synonyms);// 让近义词进行合并for (List<String> synonym : synonyms) {
    word.union(synonym.get(0), synonym.get(1));}// 分类存储近义词到 dic 中for (List<String> synonym : synonyms) {
    String parent = word.findParent(synonym.get(0));dic.putIfAbsent(parent, new HashSet<>());dic.get(parent).add(synonym.get(0));dic.get(parent).add(synonym.get(1));}// 待替换的单词数组String[] textArray = text.split(" ");dfs(ans, textArray, 0, new StringBuilder());ans.sort((a, b) -> a.compareTo(b));return ans;}/*** 从 textArray 的第 idx 个单词开始替换近义词，替换后的新句子放到 ans 中** @param ans* @param textArray* @param idx* @param sb*/private void dfs(List<String> ans, String[] textArray, int idx, StringBuilder sb) {
    if (idx == textArray.length) {
    // 已经到末尾了，全部替换完毕ans.add(sb.toString().trim());return;}// 如果当前近义词字典不存在当前单词，则跳过当前单词if (!word.map.containsKey(textArray[idx])) {
    dfs(ans, textArray, idx + 1, sb.append(" ").append(textArray[idx]));} else {
    // 获取当前待替换单词的父亲String parent = word.findParent(textArray[idx]);// 找到所有近义词HashSet<String> strings = dic.get(parent);// 当前单词用近义词代替for (String string : strings) {
    StringBuilder sbb = new StringBuilder(sb);dfs(ans, textArray, idx + 1, sbb.append(" ").append(string));}}}class Word {
    /*** key 为字符串* value 为父字符串*/Map<String, String> map;Word(List<List<String>> synonyms) {
    map = new HashMap<>();for (List<String> synonym : synonyms) {
    for (String s : synonym) {
    // 初始每个字符串的父字符串为其本身map.put(s, s);}}}void union(String s1, String s2) {
    String parent1 = findParent(s1);String parent2 = findParent(s2);if (!parent1.equals(parent2)) {
    map.put(s2, parent1);}}String findParent(String s) {
    while (!s.equals(map.get(s))) {
    s = map.get(s);}return s;}}
}