题目大意：
近义词句子
给你一个近义词表 synonyms 和一个句子 text，synonyms 表中是一些近义词对 ，你可以将句子 text 中每个单词用它的近义词来替换。
请你找出所有用近义词替换后的句子，按 字典序排序 后返回。
示例1：
输入: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday" 输出: ["I am cheerful today but was sad yesterday", "I am cheerful today but was sorrow yesterday", "I am happy today but was sad yesterday", "I am happy today but was sorrow yesterday", "I am joy today but was sad yesterday", "I am joy today but was sorrow yesterday"]
提示：
- 0 <= synonyms.length <= 10
- synonyms[i].length == 2
- synonyms[0] != synonyms[1]
- 所有单词仅包含英文字母，且长度最多为 10。
- text 最多包含 10 个单词，且单词间用单个空格分隔开。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1258
解题思路分析：
这道题目关键在于如何给近义词分组，分组后，遍历句子中的每个单词，查看与当前单词同组的近义词有哪些，这些近义词都可以替换掉当前单词。
将近义词分组时，利用题目给出的synonyms列表，这个列表的每个子列表都只有2个单词，我们可以把每个单词看做是一个节点，子列表中的2个单词可以看做是一条连线，遍历完synonyms所有元素之后，我们可以将所有单词的关系图用线连接起来，所有相连接的部分可以看做是一组。
分组之后，再遍历句子中的每个单词，查看当前单词属于哪一组，同组的单词都可以出现在当前位置，此处可以利用dfs遍历出每一条路径，即可找出所有单词的组合。
实现代码：
// 近义词的关系图
// 表示当前单词可以连接哪些近义词
Map<String, Set<String>> map = new HashMap<>();
public List<String> generateSentences(List<List<String>> synonyms, String text) {
// 构建近义词关系图
for(List<String> list : synonyms){
// 获得列表中第0个元素能够连接的单词列表
Set<String> set = map.getOrDefault(list.get(0), new HashSet<>());
// 将第1个元素添加到第0个元素能够连接的单词列表中
set.add(list.get(1));
map.put(list.get(0), set);
// 获得列表中第1个元素能够连接的单词列表
Set<String> set2 = map.getOrDefault(list.get(1), new HashSet<>());
// 将第0个元素添加到第0个元素能够连接的单词列表中
set2.add(list.get(0));
map.put(list.get(1), set2);
}
// 分组
// group表示句子text中第i个元素包含哪些近义词
Map<Integer, Set<String>> group = new HashMap<>();
String[] arr = text.split(" ");
// 利用关系图，将句子text中所有单词分组
for(int i=0;i<arr.length;i++){
Set<String> set = new HashSet<>();
// 找到所有当前单词的近义词，存入group
findSameGroupNodes(arr[i], set);
group.put(i, set);
}
// 利用分组，dfs得到所有路径（单词组合）
dfs(group,arr,0,"");
Collections.sort(res);
return res;
}
// 找到单词s的所有近义词
void findSameGroupNodes(String s, Set<String> set){
// s本身即是近义词，加入集合
set.add(s);
// 如果关系图中不包含单词s，退出
if(!map.containsKey(s)){
return;
}
// 从关系图中获得所有s的近义词。
// 为了防止递归时重复查询，将关系图中s的近义词清空
Set<String> res = map.get(s);
map.remove(s);
for(String str : res){
// 递归查找近义词的近义词。。。
findSameGroupNodes(str, set);
}
// 还原关系图中s的近义词清空
// 此处不还原的话，其他单词找近义词时就无法取得了。
map.put(s, res);
}
// 返回结果
List<String> res = new ArrayList<>();
// 利用分组信息递归每一种路径（单词组合）
// group为分组信息
// arr是将句子text转化成的字符串数组
// index为当前arr下标
// result是到当前下标为止组成的句子
void dfs(Map<Integer, Set<String>> group, String[] arr, int index, String result){
// 如果下标等于句子长度，说明所有单词位已经填充完单词
if(index==arr.length){
// 将组成的句子加入返回结果
res.add(result);
return; // 退出dfs递归
}
// 如果当前句子不是空，加上一个空格
if(result!=""){
result+=" ";
}
// 查看当前单词有哪些近义词，循环将每个近义词放入当前位置
for(String s : group.get(index)){
// dfs递归到下一层
dfs(group,arr,index+1,result+s);
}
}本题解法执行时间为3ms。
Runtime: 3 ms, faster than 74.27% of Java online submissions for Synonymous Sentences.
Memory Usage: 36.1 MB, less than 100.00% of Java online submissions for Synonymous Sentences.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1258-synonymous-sentences-解题思路分析/