2573-找出对应 LCP 矩阵的字符串

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

对任一由 n 个小写英文字母组成的字符串 word ，我们可以定义一个 n x n 的矩阵，并满足：

  • lcp[i][j] 等于子字符串 word[i,...,n-1] 和 word[j,...,n-1] 之间的最长公共前缀的长度。

给你一个 n x n 的矩阵 lcp 。返回与 lcp 对应的、按字典序最小的字符串 word 。如果不存在这样的字符串，则返回空字符串。

对于长度相同的两个字符串 a 和 b ，如果在 a 和 b 不同的第一个位置，字符串 a 的字母在字母表中出现的顺序先于 b
中的对应字母，则认为字符串 a 按字典序比字符串 b 小。例如，"aabd" 在字典上小于 "aaca"
，因为二者不同的第一位置是第三个字母，而 'b' 先于 'c' 出现。

示例 1：

**输入：** lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]
**输出：** "abab"
**解释：** lcp 对应由两个交替字母组成的任意 4 字母字符串，字典序最小的是 "abab" 。

示例 2：

**输入：** lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]
**输出：** "aaaa"
**解释：** lcp 对应只有一个不同字母的任意 4 字母字符串，字典序最小的是 "aaaa" 。

示例 3：

**输入：** lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]]
**输出：** ""
**解释：** lcp[3][3] 无法等于 3 ，因为 word[3,...,3] 仅由单个字母组成；因此，不存在答案。

提示：

  • 1 <= n == ``lcp.length == ``lcp[i].length <= 1000
  • 0 <= lcp[i][j] <= n

前言

对于给定的 n \times n 的矩阵 lcp，首先考虑其对应的字符串 word 存在的必要条件。

  1. 对于任意 0 \le i < n，lcp}[i][i] 为子串 word}[i, n - 1] 与其自身的最长公共前缀的长度，该长度应等于子串长度，因此应满足 lcp}[i][i] = n - i。如果存在 0 \le i < n 不满足 lcp}[i][i] = n - i，则字符串 word 不存在，返回空字符串。

  2. 对于任意 0 \le i < j < n，子串 word}[i, n - 1] 和 word}[j, n - 1] 的最长公共前缀的长度应等于子串 word}[j, n - 1] 和 word}[i, n - 1] 的最长公共前缀的长度，因此应满足 lcp}[i][j] = \textit{lcp}[j][i]，即矩阵 lcp 是对称矩阵。如果存在 0 \le i < j < n 不满足 lcp}[i][j] = \textit{lcp}[j][i]，则字符串 word 不存在，返回空字符串。

  3. 对于任意 0 \le i < j < n，子串 word}[i, n - 1] 和 word}[j, n - 1] 的最长公共前缀的长度不能超过其中任意一个子串的长度，即应满足 lcp}[i][j] \le n - i 且 lcp}[i][j] \le n - j，当 i < j 时 n - i > n - j，因此应满足 lcp}[i][j] \le n - j。如果存在 0 \le i < j < n 不满足 lcp}[i][j] \le n - j，则字符串 word 不存在，返回空字符串。

只有当上述必要条件都成立时，字符串 word 才可能存在，需要构造字典序最小的字符串 word，然后验证是否符合要求。

构造字符串 word 应使用贪心策略，可以基于并查集构造，也可以直接构造。

解法一

思路和算法

构造字符串 word 时，需要判断每一对下标处的字符是否相同，如果两个子串的最长公共前缀的长度大于 0 则这两个子串的首字母一定相同，如果两个子串的最长公共前缀的长度等于 0 则这两个子串的首字母一定不同。因此对于任意 0 \le i < j < n，如果 lcp}[i][j] > 0 则 word}[i] = \textit{word}[j]，如果 lcp}[i][j] = 0 则 word}[i] \ne \textit{word}[j]。可以使用集合表示字母相同的下标，如果两个下标属于相同集合则这两个下标处的字母相同，如果两个下标属于不同集合则这两个下标处的字母不同，则问题转换成根据连通分量构造字符串 word，连通性问题可以使用并查集解决。

并查集初始化时，n 个下标分别属于不同的集合。初始化之后，对于每一对下标 (i, j)，如果 lcp}[i][j] > 0 则 word}[i] = \textit{word}[j]，因此将下标 i 和下标 j 合并。遍历所有下标对之后，即可得到所有的连通分量，满足同一个连通分量对应相同字母，不同连通分量对应不同字母。

由于字符串 word 由小写字母组成，因此最多有 26 个不同字符。如果连通分量个数大于 26，则字符串 word 不存在，返回空字符串。当连通分量个数小于等于 26 时，构造字符串 word，然后验证是否符合要求。

构造字符串 word 时，应得到每个下标所属的连通分量，分别填入每个连通分量对应的字母。为了使字符串 word 的字典序最小，应使用贪心策略，从左到右遍历每个下标，当遍历到未填入字母的下标时，填入可能的字典序最小的字母。贪心策略的正确性说明如下：当遍历到未填入字母的下标 i 时，下标范围 [0, i - 1] 已经填入字母，此时填入可能的字典序最小的字母可以使字符串 word 的字典序最小，如果填入字典序更大的字母则一定会使字符串 word 的字典序更大。

构造字符串 word 的具体做法是，用 letter 表示可能的字典序最小的字母，初始时 letter} = \text{`a’。从左到右遍历每个下标，当遍历到下标 i 时，如果下标 i 未填入字母，则执行如下操作。

  1. 得到下标 i 所属的连通分量，并得到该连通分量中的所有下标。

  2. 将该连通分量中的所有下标处都填入字母 letter。

  3. 此时字母 letter 已经被使用，因此将 letter 的值更新为字典序的下一个字母。

遍历所有下标之后，字符串 word 构造完成，然后需要验证是否符合要求。可以使用动态规划验证。

用 n \times n 的二维数组 dp 表示动态规划的状态，其中 dp}[i][j] 为子串 word}[i, n - 1] 和 word}[j, n - 1] 的最长公共前缀的长度。

当 i = n - 1 或 j = n - 1 时，子串 word}[i, n - 1] 和 word}[j, n - 1] 的最长公共前缀的长度不超过 1，如果 word}[i] = \textit{word}[j] 则最长公共前缀的长度是 1，如果 word}[i] \ne \textit{word}[j] 则最长公共前缀的长度是 0。因此动态规划的边界情况是：当 word}[i] = \textit{word}[j] 时 dp}[i][j] = 1，当 word}[i] \ne \textit{word}[j] 时 dp}[i][j] = 0。

当 i < n - 1 且 j < n - 1 时，如果 word}[i] \ne \textit{word}[j] 则子串 word}[i, n - 1] 和 word}[j, n - 1] 的最长公共前缀的长度是 0，如果 word}[i] = \textit{word}[j] 则子串 word}[i, n - 1] 和 word}[j, n - 1] 的最长公共前缀的长度需要通过子串 word}[i + 1, n - 1] 和 word}[j + 1, n - 1] 的最长公共前缀的长度计算得到，在子串 word}[i + 1, n - 1] 和 word}[j + 1, n - 1] 的最长公共前缀的前面添加公共字符 word}[i] 或 word}[j] 即可得到长度增加一位的公共前缀。因此动态规划的状态转移方程如下。

  • 当 word}[i] = \textit{word}[j] 时，dp}[i][j] = \textit{dp}[i + 1][j + 1] + 1。

  • 当 word}[i] \ne \textit{word}[j] 时，dp}[i][j] = 0。

根据动态规划的状态转移方程，计算 dp}[i][j] 的顺序为从大到小遍历每个 i，对于每个 i 从大到小遍历每个 j。

实现方面，不需要创建二维数组 dp，而是可以通过给定的矩阵 lcp 验证。验证方法如下。

  • 当 word}[i] = \textit{word}[j] 时，如果出现如下情况，则字符串 word 不符合要求，返回空字符串。

    • 当 i = n - 1 或 j = n - 1 时，如果 lcp}[i][j] \ne 1，则字符串 word 不符合要求，返回空字符串。

    • 当 i < n - 1 且 j < n - 1 时，如果 lcp}[i][j] \ne \textit{lcp}[i + 1][j + 1] + 1，则字符串 word 不符合要求，返回空字符串。

  • 当 word}[i] \ne \textit{word}[j] 时，如果 lcp}[i][j] > 0，则字符串 word 不符合要求，返回空字符串。

如果字符串 word 符合要求，则返回字符串 word。

代码

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class Solution {
    public String findTheString(int[][] lcp) {
        int n = lcp.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            if (lcp[i][i] != n - i) {
                return "";
            }
            for (int j = i + 1; j < n; j++) {
                if (lcp[i][j] != lcp[j][i] || lcp[i][j] > n - j) {
                    return "";
                } else if (lcp[i][j] > 0) {
                    uf.union(i, j);
                }
            }
        }
        Map<Integer, List<Integer>> components = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < n; i++) {
            int root = uf.find(i);
            components.putIfAbsent(root, new ArrayList<Integer>());
            components.get(root).add(i);
        }
        if (components.size() > 26) {
            return "";
        }
        char[] word = new char[n];
        Arrays.fill(word, ' ');
        char letter = 'a';
        for (int i = 0; i < n; i++) {
            if (word[i] == ' ') {
                int root = uf.find(i);
                List<Integer> component = components.get(root);
                for (int index : component) {
                    word[index] = letter;
                }
                letter++;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (word[i] == word[j]) {
                    if (i == n - 1 || j == n - 1) {
                        if (lcp[i][j] != 1) {
                            return "";
                        }
                    } else if (lcp[i][j] != lcp[i + 1][j + 1] + 1) {
                        return "";
                    }
                } else if (lcp[i][j] > 0) {
                    return "";
                }
            }
        }
        return new String(word);
    }
}

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        rank = new int[n];
    }

    public void union(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            if (rank[rootx] > rank[rooty]) {
                parent[rooty] = rootx;
            } else if (rank[rootx] < rank[rooty]) {
                parent[rootx] = rooty;
            } else {
                parent[rooty] = rootx;
                rank[rootx]++;
            }
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
public class Solution {
    public string FindTheString(int[][] lcp) {
        int n = lcp.Length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            if (lcp[i][i] != n - i) {
                return "";
            }
            for (int j = i + 1; j < n; j++) {
                if (lcp[i][j] != lcp[j][i] || lcp[i][j] > n - j) {
                    return "";
                } else if (lcp[i][j] > 0) {
                    uf.Union(i, j);
                }
            }
        }
        IDictionary<int, IList<int>> components = new Dictionary<int, IList<int>>();
        for (int i = 0; i < n; i++) {
            int root = uf.Find(i);
            components.TryAdd(root, new List<int>());
            components[root].Add(i);
        }
        if (components.Count > 26) {
            return "";
        }
        char[] word = new char[n];
        Array.Fill(word, ' ');
        char letter = 'a';
        for (int i = 0; i < n; i++) {
            if (word[i] == ' ') {
                int root = uf.Find(i);
                IList<int> component = components[root];
                foreach (int index in component) {
                    word[index] = letter;
                }
                letter++;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (word[i] == word[j]) {
                    if (i == n - 1 || j == n - 1) {
                        if (lcp[i][j] != 1) {
                            return "";
                        }
                    } else if (lcp[i][j] != lcp[i + 1][j + 1] + 1) {
                        return "";
                    }
                } else if (lcp[i][j] > 0) {
                    return "";
                }
            }
        }
        return new string(word);
    }
}

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        rank = new int[n];
    }

    public void Union(int x, int y) {
        int rootx = Find(x);
        int rooty = Find(y);
        if (rootx != rooty) {
            if (rank[rootx] > rank[rooty]) {
                parent[rooty] = rootx;
            } else if (rank[rootx] < rank[rooty]) {
                parent[rootx] = rooty;
            } else {
                parent[rooty] = rootx;
                rank[rootx]++;
            }
        }
    }

    public int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }
}

复杂度分析

  • 时间复杂度：O(n^2 \times \alpha(n))，其中 n 是矩阵 lcp 的行数和列数，\alpha 是反阿克曼函数。判断必要条件是否成立需要 O(n^2) 的时间，并查集的初始化需要 O(n) 的时间，初始化之后需要执行 O(n^2) 次合并操作，计算每个连通分量中的所有下标和构造字符串 word 需要执行 O(n) 次查找操作，验证字符串 word 是否符合要求需要 O(n^2) 的时间，这里的并查集使用了路径压缩和按秩合并，单次操作的时间复杂度是 O(\alpha(n))，因此时间复杂度是 O(n^2 \times \alpha(n))。

  • 空间复杂度：O(n)，其中 n 是矩阵 lcp 的行数和列数。并查集、存储每个连通分量中的所有下标的哈希表和构造的字符串需要 O(n) 的空间。

解法二

思路和算法

也可以不使用并查集，直接构造字符串 word。字符串 word 应满足：对于任意 0 \le i < j < n，如果 lcp}[i][j] > 0 则 word}[i] = \textit{word}[j]，如果 lcp}[i][j] = 0 则 word}[i] \ne \textit{word}[j]。

用 remain 表示未填入字母的下标个数，用 letter 表示可能的字典序最小的字母，初始时 remain} = n，letter} = \text{`a’。从左到右遍历每个下标，当遍历到未填入字母的下标 i 时，执行如下操作。

  1. 从左到右遍历下标范围 [i, n - 1] 的每个下标，当遍历到下标 j 时，如果 lcp}[i][j] > 0 且 word}[j] 未填入字母，则将字母 letter 填入 word}[j]，将 remain 的值减 1。

  2. 当 i < n 且 word}[i] 已填入字母时，将 i 的值加 1，直到 i \ge n 或 word}[i] 未填入字母。

  3. 此时字母 letter 已经被使用，因此将 letter 的值更新为字典序的下一个字母。

重复上述操作，直到 letter} > \text{`z’ 或 remain} = 0 时结束构造。

结束构造时，如果 remain} > 0，则无法使用 26 个小写字母填入字符串 word 的所有下标，因此字符串 word 不存在，返回空字符串。

如果 remain} = 0，则字符串 word 构造完成，然后需要验证是否符合要求。可以使用动态规划验证。验证方法同解法一。

如果验证过程中发现字符串 word 不符合要求，则返回空字符串。如果字符串 word 符合要求，则返回字符串 word。

代码

[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public String findTheString(int[][] lcp) {
        int n = lcp.length;
        for (int i = 0; i < n; i++) {
            if (lcp[i][i] != n - i) {
                return "";
            }
            for (int j = i + 1; j < n; j++) {
                if (lcp[i][j] != lcp[j][i] || lcp[i][j] > n - j) {
                    return "";
                }
            }
        }
        char[] word = new char[n];
        Arrays.fill(word, ' ');
        int remain = n;
        char letter = 'a';
        for (int i = 0; letter <= 'z' && remain > 0; letter++) {
            for (int j = i; j < n; j++) {
                if (lcp[i][j] > 0 && word[j] == ' ') {
                    word[j] = letter;
                    remain--;
                }
            }
            while (i < n && word[i] != ' ') {
                i++;
            }
        }
        if (remain > 0) {
            return "";
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (word[i] == word[j]) {
                    if (i == n - 1 || j == n - 1) {
                        if (lcp[i][j] != 1) {
                            return "";
                        }
                    } else if (lcp[i][j] != lcp[i + 1][j + 1] + 1) {
                        return "";
                    }
                } else if (lcp[i][j] > 0) {
                    return "";
                }
            }
        }
        return new String(word);
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class Solution {
    public string FindTheString(int[][] lcp) {
        int n = lcp.Length;
        for (int i = 0; i < n; i++) {
            if (lcp[i][i] != n - i) {
                return "";
            }
            for (int j = i + 1; j < n; j++) {
                if (lcp[i][j] != lcp[j][i] || lcp[i][j] > n - j) {
                    return "";
                }
            }
        }
        char[] word = new char[n];
        Array.Fill(word, ' ');
        int remain = n;
        char letter = 'a';
        for (int i = 0; letter <= 'z' && remain > 0; letter++) {
            for (int j = i; j < n; j++) {
                if (lcp[i][j] > 0 && word[j] == ' ') {
                    word[j] = letter;
                    remain--;
                }
            }
            while (i < n && word[i] != ' ') {
                i++;
            }
        }
        if (remain > 0) {
            return "";
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (word[i] == word[j]) {
                    if (i == n - 1 || j == n - 1) {
                        if (lcp[i][j] != 1) {
                            return "";
                        }
                    } else if (lcp[i][j] != lcp[i + 1][j + 1] + 1) {
                        return "";
                    }
                } else if (lcp[i][j] > 0) {
                    return "";
                }
            }
        }
        return new string(word);
    }
}

复杂度分析

  • 时间复杂度：O(n^2)，其中 n 是矩阵 lcp 的行数和列数。判断必要条件是否成立需要 O(n^2) 的时间，构造字符串 word 需要 O(n^2) 的时间，验证字符串 word 是否符合要求需要 O(n^2) 的时间，因此时间复杂度是 O(n^2)。

  • 空间复杂度：O(n)，其中 n 是矩阵 lcp 的行数和列数。存储构造的字符串需要 O(n) 的空间。

 Comments
On this page
2573-找出对应 LCP 矩阵的字符串
  1. 前言
  2. 解法一
    1. 思路和算法
    2. 代码
    3. 复杂度分析
  3. 解法二
    1. 思路和算法
    2. 代码
    3. 复杂度分析