难度: Medium
Submission
运行时间: 35 ms
内存: 16.1 MB
class Solution:
def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:
byPrefix, bySuffix = defaultdict(list), defaultdict(list)
for i, s in enumerate(phrases):
j = s.find(' ')
prefix = s[:j] if j >= 0 else s
k = s.rfind(' ')
suffix = s[k+1:] if k >=0 else s
byPrefix[prefix].append(i)
bySuffix[suffix].append(i)
res = set()
for k in set(byPrefix.keys()) & set(bySuffix.keys()):
sufLst, preLst = bySuffix[k], byPrefix[k]
lenK = len(k)
for s, p in product(sufLst, preLst):
if s != p:
res.add(phrases[s] + phrases[p][lenK:])
return sorted(res)
Explain
该题解的思路是使用两个字典来分别存储每个短语的前缀和后缀。然后，检查所有前缀和后缀是否有相同的部分，如果有，则将对应的短语拼接在一起。最后，返回排序后的结果集。
时间复杂度: O(n^2m)
空间复杂度: O(n^2m)
class Solution:
def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:
byPrefix, bySuffix = defaultdict(list), defaultdict(list)
for i, s in enumerate(phrases):
j = s.find(' ')
prefix = s[:j] if j >= 0 else s
k = s.rfind(' ')
suffix = s[k+1:] if k >=0 else s
byPrefix[prefix].append(i)
bySuffix[suffix].append(i)
res = set()
for k in set(byPrefix.keys()) & set(bySuffix.keys()):
sufLst, preLst = bySuffix[k], byPrefix[k]
lenK = len(k)
for s, p in product(sufLst, preLst):
if s != p:
res.add(phrases[s] + phrases[p][lenK:])
return sorted(res)
Explore
在这个问题中，字典（即哈希表）被用来高效地存储和查询前缀和后缀。使用字典可以快速匹配相同的前缀或后缀，因为字典提供平均常数时间复杂度的查找性能。如果使用数组，则需要遍历数组来查找匹配项，这会导致更高的时间复杂度。此外，由于每个前缀和后缀可以对应多个短语，使用字典存储索引列表（即短语的位置）是管理这种多对多关系的有效方式。
在代码中，前缀是通过寻找第一个空格（如果存在）来确定的，后缀则是通过寻找最后一个空格来确定的。如果短语中没有空格（即`j`或`k`为-1），则整个短语既是前缀也是后缀。这种方法自然处理了包含多个空格或无空格的短语，确保前缀和后缀总是根据短语的实际结构被正确地切割。
在算法中，只有当短语A的后缀与短语B的前缀完全相同时才会进行拼接，这确保了拼接的正确性和无缝性。因为这种情况下，两个短语在拼接点共享相同的单词，从而自然避免了重叠或冲突问题。此外，拼接后的字符串从短语A的开始到短语B的结束，中间的共享单词不会重复。
条件`if s != p`确保不会将同一短语与自身拼接，避免产生无意义的结果如重复相同短语。此条件只是为了确保短语的索引不相等，从而防止自我拼接。这不会漏掉任何有效的拼接组合，因为有效的组合需要两个不同的短语通过共享的前缀/后缀来进行拼接。