X

LEETCODE 1181. Before and After Puzzle 解题思路分析

题目大意:

前后拼接

给你一个「短语」列表 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 <= 100
  • 1 <= 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-解题思路分析/
Categories: leetcode
kwantong: