OA回顾 之 拼接可得的最长字符串长度

关于OA回顾

这个系列旨在记录参加过的一些日本互联网公司的OA原题。考虑到私密性等问题，文中只会记录题目的内容而不会指明该题来自于哪一家公司。

题目概述

现有一个字符串数组strings，数组中的字符串均由小写英文字母构成。对于数组中任意两个不同的字符串，如果它们满足：其中一个字符串末尾的两个字符（以下简称后缀）与另一个字符串开头的两个字符（以下简称前缀）相同，则可以对它们进行一次首尾拼接，拼接时相同的前缀与后缀部分共有。每一个字符串最多可以拼接一次。

求：利用该数组中的字符串拼接后可以得到的最长字符串的长度。

限制条件：

• 1 <= strings.length <= 10 ^ 5
• strings中的所有字符串均不相同
• 2 <= strings[i].length <= 20

例：

Input: strings = ["aaaa", "akkj", "kjiol", "cc", "kjkjkjkjkj"]
Output: 13 ("kjkjkjkjkj" + "iol")

思路 & 代码实现

解法一：Brute Force

暴力解法可以总结为以下几步：

• 声明变量ans用于存储结果。
• 遍历strings，建立一个以其中的字符串前缀为key，对应前缀的字符串在其中的索引的列表为值的哈希表prefix_table。
• 再一次遍历strings，判断当前字符串的后缀是否作为key存在于prefix_table中。
  • 如果存在，则遍历对应key的索引列表，当对应索引的字符串与当前字符串不同时，计算拼接后长度并更新ans的值。
• 返回ans的值。

代码实现如下：

from collections import defaultdict

def maximumConcatenateLength(strings):
    ans = 0
    prefix_table = defaultdict(list)

    for i, s in enumerate(strings):
        prefix = s[:2]
        prefix_table[prefix].append(i)

    for s in strings:
        suffix = s[-2:]
        if suffix in prefix_table:
            for i in prefix_table[suffix]:
                if strings[i] != s:
                    ans = max(ans, len(strings[i]) + len(s) - 2)

    return ans

Time complexity: $O(n ^ 2)$

Space complexity: $O(n)$

可以看到暴力解法虽然能够保证算法逻辑正确，但时间复杂度高，在实际的OA中无法做到AC。

解法二：哈希表优化

因为题目只要求得出拼接得到的最长字符串的长度，所以实际上在哈希表中只需要存储对应前（后）缀的字符串中最长的那一个的长度即可，也即贪心算法的思想。这一步可以通过以下代码实现：

from collections import defaultdict

prefix_table, suffix_table = defaultdict(int), defaultdict(int)

for s in strings:
    prefix, suffix = s[:2], s[-2:]
    prefix_table[prefix] = max(prefix_table[prefix], len(s))
    suffix_table[suffix] = max(suffix_table[suffix], len(s))

但与此同时也会产生新的问题：如果对应前（后）缀中最长的那一个字符串的前后缀相同，那么在不改动原有算法的情况下它将会与自己进行拼接，而这是不被允许的。我想这也是本题的难点所在。为了避免这种自我拼接的情况发生，我们可以将前后缀相同的字符串单独存储在一个新的哈希表common_table中：

from collections import defaultdict

# 新增哈希表common_table
prefix_table, suffix_table, common_table = defaultdict(int), defaultdict(int), defaultdict(int)

for s in strings:
    prefix, suffix = s[:2], s[-2:]
    # 前后缀相同的字符串的最大长度存储在common_table中
    if prefix == suffix:
        common_table[prefix] = max(common_table[prefix], len(s))
    else:
        prefix_table[prefix] = max(prefix_table[prefix], len(s))
        suffix_table[suffix] = max(suffix_table[suffix], len(s))

接下来考虑所有可能的拼接情况，有三种：

• suffix_table中对应后缀 + prefix_table中对应前缀
• suffix_table中对应后缀 + common_table中对应前缀
• common_table中对应后缀 + prefix_table中对应前缀

注意common_table中对应后缀 + common_table中对应前缀的情况是不成立的，因为这是在与自己拼接。

代码实现如下：

ans = 0

for suffix, length in suffix_table.items():
    if suffix in prefix_table:
        ans = max(ans, length + len(prefix_table[suffix]) - 2)
    if suffix in common_table:
        ans = max(ans, length + len(common_table[suffix]) - 2)

for suffix, length in common_table.items():
    if suffix in prefix_table:
        ans = max(ans, length + len(prefix_table[suffix]) - 2)

return ans

总结

完整题解如下：

from collections import defaultdict

def maximumConcatenateLength(strings):
    prefix_table, suffix_table, common_table = defaultdict(int), defaultdict(int), defaultdict(int)
    ans = 0

    for s in strings:
        prefix, suffix = s[:2], s[-2:]
        if prefix == suffix:
            common_table[prefix] = max(common_table[prefix], len(s))
        else:
            prefix_table[prefix] = max(prefix_table[prefix], len(s))
            suffix_table[suffix] = max(suffix_table[suffix], len(s))

    for suffix, length in suffix_table.items():
        if suffix in prefix_table:
            ans = max(ans, length + prefix_table[suffix] - 2)
        if suffix in common_table:
            ans = max(ans, length + common_table[suffix] - 2)

    for suffix, length in common_table.items():
        if suffix in prefix_table:
            ans = max(ans, length + prefix_table[suffix] - 2)

    return ans

Time complexity: $O(n)$

Space complexity: $O(n)$

本题涉及了字符串处理、哈希表以及贪心算法的知识点，在避免重复项操作上需要一定的思考深度，想要在规定的时间内做到AC还是有些许难度。