Find the String with LCP
We define the lcp matrix of any 0-indexed string word of n lowercase English letters as an n x n grid such that:
lcp[i][j]is equal to the length of the longest common prefix between the substringsword[i, n - 1]andword[j, n - 1].
Given an n x n matrix lcp, return the alphabetically smallest string word that corresponds to lcp. If there is no such string, return an empty string.
A string a is lexicographically smaller than a string b of the same length if, in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.
Example 1
Input
lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]Output
"abab"lcp corresponds to any 4 letter string with two alternating letters, and the lexicographically smallest of them is "abab".
Example 2
Input
lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]Output
"aaaa"lcp corresponds to any 4 letter string with a single distinct letter, and the lexicographically smallest of them is "aaaa".
Constraints
- 1 <= n == lcp.length == lcp[i].length <= 1000
- 0 <= lcp[i][j] <= n