跳转至

LeetCode: 1181. 前后拼接

1、题目描述

给你一个「短语」列表 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:

输入:phrases = ["a","b","a"]
输出:["a"]

提示:

  • 1 <= phrases.length <= 100
  • 1 <= phrases[i].length <= 100

2、解题思路

  • 使用字典记住以当前单词开头,以当前单词结尾的,进行笛卡尔积

  • 需要处理下面特殊情况

    • 首尾字母相同,使用index做标识,同一个句子不能连接本身
from collections import defaultdict
from itertools import product


class Solution:
    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:
        before = defaultdict(set)
        after = defaultdict(set)

        for index, f in enumerate(phrases):
            current = f.split()
            before[current[0]].add((" " + " ".join(current[1:]) if len(current) > 1 else "", index))
            after[current[-1]].add((f, index))

        ans = set()
        for last, words in after.items():
            if before[last]:
                ans.update(set([a + b for ((a, a_index), (b, b_index)) in product(words, before[last]) if a_index != b_index]))

        return sorted(ans)