#2573
Find the String with LCP
international master · 1920 · lc hard +32 · verified · 32.5% accepted · 206 likes · top 10%
Description
The LCP matrix of an n-character string word is an n x n grid where lcp[i][j] equals the length of the longest common prefix of the suffixes starting at positions i and j. Given such a matrix lcp, reconstruct and return the lexicographically smallest word consistent with it, or return an empty string if no valid string exists.
Example 1:
Input: lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]
Output: "abab"
Explanation: lcp corresponds to any 4 letter string with two alternating letters. 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"
Explanation: lcp corresponds to any 4 letter string with a single distinct letter. The lexicographically smallest of them is "aaaa".
Example 3:
Input: lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]]
Output: ""
Explanation: lcp[3][3] cannot be equal to 3 since word[3,...,3] consists of only a single letter; Thus, no answer exists.
Code
1
2
3