Back to Leetcode

Readme

Greedy/2573.Find-the-String-with-LCP/Readme.md

latest1.6 KB
Original Source

2573.Find-the-String-with-LCP

首先,我们知道,如果lcp[i][j]>=0,那么一定意味着s[i]==s[j],这意味着我们知道任意两个字符是否相等的信息。假设LCP的信息是准确的,那么仅凭这些信息我们就可以充分地构造出字符串来。

我们先考察s中第一个未填写的位置i,此时必然是s[0]。由于我们只有字符相等的约束,而没有字符大小的约束,所以为了构造字典序最小的字符串,我们必然将s[0]填写为'a'。此时我们只需要考察所有lcp[0][j]>0的位置j,那么必然有s[j]=s[0]='a'。当然如果我们发现s[j]已经被填写过了且不是'a',那么说明引出了矛盾,可以直接返回无解。

接下来我们考察s中第二个未填写的字符i。注意这个位置可能不一定是s[1],因为s[1]可能已经由于一些相等关系的约束而已经填写了。同样,为了使得字典序最小,我们必然将s[i]置为'b'。此时我们只需要考察所有lcp[i][j]>0的位置j,那么必然有s[j]=s[i]='b'。当然如果我们发现s[j]已经被填写过了且不是'b',那么说明引出了矛盾,可以直接返回无解。

依次类推,我们可以将26个字母顺次填入s未填充的位置上。如果最后还有一些位置没有填充完,说明无法用26个英文字符完成任务。

以上得到的s是基于LCP可信赖的前提。但是LCP本身可能是有问题的,比如lcp[0][2]=3但是lcp[1][3]=4,这样的信息是矛盾的。所以我们还需要检验基于s的LCP矩阵的准确性。求任意两个位置的LCP,这本质就是求一个双序列的DP,用两层循环即可实现。