Leetcode每日一题 —— 2573. 找出对应 LCP 矩阵的字符串
- 内容介绍
- 文章标签
- 相关推荐
问题描述：
力扣 LeetCode
2573. 找出对应 LCP 矩阵的字符串 - 力扣（LeetCode）
2573. 找出对应 LCP 矩阵的字符串 - 对任一由 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...
思路
题目到不是太难
- 根据lcp，如果
chr[i]=chr[j]那么lcp[i][j]>0，可以确定这个字符的内容。(PS，如果超过26位字符要返回空字符串) - 之前我们通过第一个字符是否相同做了判断，长度是否一致无法确定，所以要进行验证。
- 对角线肯定是n-1..1
- 对角线分割的上下三角对称
- 只验证上三角或者下三角。如果字符不相同，
lcp[i][j]=0。否则lcp[i][j]=lcp[i+1][j+1]+1（边界为lcp[x][n-1]=1
PS 通过递推dp[i][j]时间复杂度也是一样的。
问题描述：
力扣 LeetCode
2573. 找出对应 LCP 矩阵的字符串 - 力扣（LeetCode）
2573. 找出对应 LCP 矩阵的字符串 - 对任一由 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...
思路
题目到不是太难
- 根据lcp，如果
chr[i]=chr[j]那么lcp[i][j]>0，可以确定这个字符的内容。(PS，如果超过26位字符要返回空字符串) - 之前我们通过第一个字符是否相同做了判断，长度是否一致无法确定，所以要进行验证。
- 对角线肯定是n-1..1
- 对角线分割的上下三角对称
- 只验证上三角或者下三角。如果字符不相同，
lcp[i][j]=0。否则lcp[i][j]=lcp[i+1][j+1]+1（边界为lcp[x][n-1]=1
PS 通过递推dp[i][j]时间复杂度也是一样的。