题目大意：
前后拼接
给你一个「短语」列表 phrases，请你帮忙按规则生成拼接后的「新短语」列表。
「短语」（phrase）是仅由小写英文字母和空格组成的字符串。「短语」的开头和结尾都不会出现空格，「短语」中的空格不会连续出现。
「前后拼接」（Before and After puzzles）是合并两个「短语」形成「新短语」的方法。我们规定拼接时，第一个短语的最后一个单词 和 第二个短语的第一个单词 必须相同。
返回每两个「短语」 phrases[i] 和 phrases[j]（i != j）进行「前后拼接」得到的「新短语」。
注意，两个「短语」拼接时的顺序也很重要，我们需要同时考虑这两个「短语」。另外，同一个「短语」可以多次参与拼接，但「新短语」不能再参与拼接。
请你按字典序排列并返回「新短语」列表，列表中的字符串应该是 不重复的 。
示例1：
输入: phrases = ["writing code","code rocks"] 输出: ["writing code rocks"]
示例2：
输入: phrases = ["mission statement",
"a quick bite to eat",
"a chip off the old block",
"chocolate bar",
"mission impossible",
"a man on a mission",
"block party",
"eat my words",
"bar of soap"]
输出: ["a chip off the old block party",
"a man on a mission impossible",
"a man on a mission statement",
"a quick bite to eat my words",
"chocolate bar of soap"]示例3：
Input: phrases = ["a","b","a"] Output: ["a"]
提示：
1 <= phrases.length <= 1001 <= phrases[i].length <= 100
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1181
解题思路分析：
这道题并不难，我们先整理一下数据，统计出以每个句子开头的单词能组成哪些句子，然后再遍历每一个句子，用句子中的尾单词去找以该单词开头的句子，将两者合并加入返回结果即可。
实现代码：
// 统计以某个单词开头的句子有哪些
Map<String, List<Integer>> map = new HashMap<>();
public List<String> beforeAndAfterPuzzles(String[] phrases) {
// 循环每个句子
for(int i=0;i<phrases.length;i++){
// 将句子以空格分割
String[] arr = phrases[i].split(" ");
// 得到句子首单词，并将本句子加入以该首单词开始的句子集合中
List<Integer> list=map.getOrDefault(arr[0],new ArrayList<>());
list.add(i);
map.put(arr[0],list);
}
// 再次循环每个句子
for(int i=0;i<phrases.length;i++){
// 查找能与当前句子合并的句子
find(phrases,i);
}
// 返回结果
List<String> res = new ArrayList<>(set);
// 按照字典顺序排序
Collections.sort(res);
return res;
}
Set<String> set = new HashSet<>();
// 查找能与当前句子合并的句子
void find(String[] phrases, int index){
// 将当前句子以空格分割
String[] arr = phrases[index].split(" ");
// 当前句子尾单词
String key = arr[arr.length-1];
// 如果map中不存在以当前尾单词开头的句子，退出
if(!map.containsKey(key)) return;
// 找到所有以当前尾单词开头的句子
for(int i : map.get(key)){
// 注意不能与自身合并
if(i!=index){
// 合并两个句子
String str=phrases[index]+phrases[i].substring(key.length());
set.add(str);
}
}
}本题解法执行时间为7ms。
Runtime: 7 ms, faster than 72.63% of Java online submissions for Before and After Puzzle.
Memory Usage: 38.8 MB, less than 100.00% of Java online submissions for Before and After Puzzle.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1181-before-and-after-puzzle-解题思路分析/