对任一由 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<= 10000 <= lcp[i][j] <= n
方法一：贪心 + 构造
由于构造的字符串要求字典序最小，因此我们可以从字符 'a' 开始，填充到字符串
如果当前位置 'a' 填充到 'a'。然后我们将字符 'a' 的 ASCII 码加一，继续填充剩余未填充的位置。
填充结束后，如果字符串中存在未填充的位置，说明无法构造出对应的字符串，返回空字符串。
接下来，我们可以从大到小枚举字符串中的每个位置
- 如果
$s[i] = s[j]$ ，此时我们需要判断$i$ 和$j$ 是否为字符串的最后一个位置，如果是，那么$lcp[i][j]$ 应该等于$1$ ，否则$lcp[i][j]$ 应该等于$0$ 。如果不满足上述条件，说明无法构造出对应的字符串，返回空字符串。如果$i$ 和$j$ 不是字符串的最后一个位置，那么$lcp[i][j]$ 应该等于$lcp[i + 1][j + 1] + 1$ ，否则说明无法构造出对应的字符串，返回空字符串。 - 否则，如果
$lcp[i][j] \gt 0$ ，说明无法构造出对应的字符串，返回空字符串。
如果字符串中的每个位置都满足上述条件，那么我们就可以构造出对应的字符串，返回即可。
时间复杂度为
class Solution:
def findTheString(self, lcp: List[List[int]]) -> str:
n = len(lcp)
s = [""] * n
i = 0
for c in ascii_lowercase:
while i < n and s[i]:
i += 1
if i == n:
break
for j in range(i, n):
if lcp[i][j]:
s[j] = c
if "" in s:
return ""
for i in range(n - 1, -1, -1):
for j in range(n - 1, -1, -1):
if s[i] == s[j]:
if i == n - 1 or j == n - 1:
if lcp[i][j] != 1:
return ""
elif lcp[i][j] != lcp[i + 1][j + 1] + 1:
return ""
elif lcp[i][j]:
return ""
return "".join(s)class Solution {
public String findTheString(int[][] lcp) {
int n = lcp.length;
char[] s = new char[n];
int i = 0;
for (char c = 'a'; c <= 'z'; ++c) {
while (i < n && s[i] != '\0') {
++i;
}
if (i == n) {
break;
}
for (int j = i; j < n; ++j) {
if (lcp[i][j] > 0) {
s[j] = c;
}
}
}
for (i = 0; i < n; ++i) {
if (s[i] == '\0') {
return "";
}
}
for (i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (s[i] == s[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 String.valueOf(s);
}
}class Solution {
public:
string findTheString(vector<vector<int>>& lcp) {
int i = 0, n = lcp.size();
string s(n, '\0');
for (char c = 'a'; c <= 'z'; ++c) {
while (i < n && s[i]) {
++i;
}
if (i == n) {
break;
}
for (int j = i; j < n; ++j) {
if (lcp[i][j]) {
s[j] = c;
}
}
}
if (s.find('\0') != -1) {
return "";
}
for (i = n - 1; ~i; --i) {
for (int j = n - 1; ~j; --j) {
if (s[i] == s[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]) {
return "";
}
}
}
return s;
}
};func findTheString(lcp [][]int) string {
i, n := 0, len(lcp)
s := make([]byte, n)
for c := 'a'; c <= 'z'; c++ {
for i < n && s[i] != 0 {
i++
}
if i == n {
break
}
for j := i; j < n; j++ {
if lcp[i][j] > 0 {
s[j] = byte(c)
}
}
}
if bytes.IndexByte(s, 0) >= 0 {
return ""
}
for i := n - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
if s[i] == s[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 string(s)
}