最长公共后缀查询

难度: Hard

给你两个字符串数组 wordsContainer 和 wordsQuery 。

对于每个 wordsQuery[i] ，你需要从 wordsContainer 中找到一个与 wordsQuery[i] 有 最长公共后缀 的字符串。如果 wordsContainer 中有两个或者更多字符串有最长公共后缀，那么答案为长度最短的。如果有超过两个字符串有相同最短长度，那么答案为它们在 wordsContainer 中出现更早的一个。

请你返回一个整数数组 ans ，其中 ans[i]是 wordsContainer中与 wordsQuery[i] 有 最长公共后缀 字符串的下标。

示例 1：

输入：wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]

输出：[1,1,1]

解释：

我们分别来看每一个 wordsQuery[i] ：

对于 wordsQuery[0] = "cd" ，wordsContainer 中有最长公共后缀 "cd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
对于 wordsQuery[1] = "bcd" ，wordsContainer 中有最长公共后缀 "bcd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
对于 wordsQuery[2] = "xyz" ，wordsContainer 中没有字符串跟它有公共后缀，所以最长公共后缀为 "" ，下标为 0 ，1 和 2 的字符串都得到这一公共后缀。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。

示例 2：

输入：wordsContainer = ["abcdefgh","poiuygh","ghghgh"], wordsQuery = ["gh","acbfgh","acbfegh"]

输出：[2,0,2]

解释：

我们分别来看每一个 wordsQuery[i] ：

对于 wordsQuery[0] = "gh" ，wordsContainer 中有最长公共后缀 "gh" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。
对于 wordsQuery[1] = "acbfgh" ，只有下标为 0 的字符串有最长公共后缀 "fgh" 。所以尽管下标为 2 的字符串是最短的字符串，但答案是 0 。
对于 wordsQuery[2] = "acbfegh" ，wordsContainer 中有最长公共后缀 "gh" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。

提示：

1 <= wordsContainer.length, wordsQuery.length <= 10⁴
1 <= wordsContainer[i].length <= 5 * 10³
1 <= wordsQuery[i].length <= 5 * 10³
wordsContainer[i] 只包含小写英文字母。
wordsQuery[i] 只包含小写英文字母。
wordsContainer[i].length 的和至多为 5 * 10⁵ 。
wordsQuery[i].length 的和至多为 5 * 10⁵ 。

Submission

运行时间: 179 ms

内存: 28.7 MB


class Solution:
    def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) -> List[int]:
        wordsContainer = [w[::-1] for w in wordsContainer]
        wordsQuery = [w[::-1] for w in wordsQuery]
        ret = [-1] * len(wordsQuery)

        def f(wc: List[int], wq: List[int], zidx: int) -> None:
            if len(wc) == 1:
                for qidx in wq:
                    ret[qidx] = wc[0]
            else:
                nxt = defaultdict(lambda: ([], []))
                lst = []
                for cidx in wc:
                    if len(wordsContainer[cidx]) > zidx:
                        nxt[wordsContainer[cidx][zidx]][0].append(cidx)
                    else:
                        lst.append(cidx)
                for qidx in wq:
                    if len(wordsQuery[qidx]) > zidx and wordsQuery[qidx][zidx] in nxt:
                            nxt[wordsQuery[qidx][zidx]][1].append(qidx)
                    else:
                        if len(lst):
                            ret[qidx] = lst[0]
                        else:
                            ret[qidx] = wc[0]
                for v in nxt.values():
                    if len(v[1]):
                        f(v[0], v[1], zidx + 1)
        wcidx = list(range(len(wordsContainer)))
        wcidx.sort(key=lambda x: (len(wordsContainer[x]), x))

        f(wcidx, list(range(len(wordsQuery))), 0)
        return ret

Explain

此题解使用了基于字符匹配的分治递归策略，通过Trie（字典树）的思想来解决问题。首先，将wordsContainer和wordsQuery中的所有字符串逆序，目的是将最长公共后缀问题转换为字符串前缀匹配问题，这样可以利用Trie树的性质进行处理。在递归函数f中，对于当前层的字符索引zidx，将容器wordsContainer中的字符串根据当前字符分组，相同的字符分到同一个组中，没有当前字符的字符串（即短于zidx的字符串）放入一个单独的列表中。对于每一个查询字符串，根据其当前字符进行匹配：如果匹配到相应的字符组，则对这个组递归处理；如果没有匹配到，则在短字符串列表中选择一个（如果存在）。递归终止的条件是当只剩一个字符串需要处理时，直接将其分配给所有对应的查询。此策略有效地将大问题分解为小问题，递归地解决每一层的匹配问题。

时间复杂度: O(n * l + m * l)

空间复杂度: O(n * l + m * l)

class Solution:
    def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) -> List[int]:
        # Reverse all words to transform the problem to a prefix matching problem
        wordsContainer = [w[::-1] for w in wordsContainer]
        wordsQuery = [w[::-1] for w in wordsQuery]
        ret = [-1] * len(wordsQuery)

        def f(wc: List[int], wq: List[int], zidx: int) -> None:
            # If there is only one word, assign it to all queries
            if len(wc) == 1:
                for qidx in wq:
                    ret[qidx] = wc[0]
            else:
                nxt = defaultdict(lambda: ([], []))
                lst = []
                for cidx in wc:
                    if len(wordsContainer[cidx]) > zidx:
                        nxt[wordsContainer[cidx][zidx]][0].append(cidx)
                    else:
                        lst.append(cidx)
                for qidx in wq:
                    if len(wordsQuery[qidx]) > zidx and wordsQuery[qidx][zidx] in nxt:
                        nxt[wordsQuery[qidx][zidx]][1].append(qidx)
                    else:
                        if len(lst):
                            ret[qidx] = lst[0]
                        else:
                            ret[qidx] = wc[0]
                for v in nxt.values():
                    if len(v[1]):
                        f(v[0], v[1], zidx + 1)
        # Sort words by length and index for optimal performance
        wcidx = list(range(len(wordsContainer)))
        wcidx.sort(key=lambda x: (len(wordsContainer[x]), x))

        f(wcidx, list(range(len(wordsQuery))), 0)
        return ret

Explore

将字符串逆序是为了将最长公共后缀问题转化为更易处理的最长公共前缀问题。在数据结构中，字典树（Trie树）是处理字符串前缀匹配问题的常用方式，其可以高效地通过逐字符比较来搜索和匹配字符串的公共前缀。通过逆序，我们可以重新利用字典树的这一特性来处理后缀匹配问题，从而使得算法更加直观和简洁。

在实现中，为了确保在有多个字符串满足条件时返回最短的字符串，算法首先会根据字符串长度和索引对wordsContainer中的字符串进行排序。这样，在递归函数f中，当出现无法继续匹配当前字符的情况时，优先选择的是列表lst中的第一个元素，即最短的字符串。这一设计确保了在满足最长公共后缀的字符串中，返回的是长度最短的一个。

是的，这种情况有可能发生。在递归函数f中，当当前字符无法匹配时，算法会选择短字符串列表lst中的第一个字符串作为结果。这可能不是实际具有最长公共后缀的字符串，尤其是当短字符串列表中的字符串并不包含其他更长字符串中的公共后缀时。这种方法在某些情况下可能会牺牲结果的准确性，以换取算法的简化和执行效率。