作者推荐
【深度优先搜索】【树】【有向图】【推荐】685. 冗余连接 II
本文涉及知识点
字符串 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 不同的第一个位置，字符串 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
LPC
word串 如果有m个不同字符，则一定是[‘a’+0,‘a’+m) 。否则换成更小的字符，字典序更小。
如果存在合法串，则word[0]一定是a，如果lcp[0][x] >=1 ，则word[x]也是’a’
word中第一个未处理的字符是’b’⋯ \cdots⋯
⋯ \cdots⋯
如果用到第27个字符，则非法。
最后将结果串求lcp，看是否一致，不一致，也返回非法。
代码
核心代码
//最长公共前缀(Longest Common Prefix) class CLCP { public: CLCP(const string& str1, const string& str2) { m_dp.assign(str1.length() , vector<int>(str2.length())); //str1[j...)和str2[k...]比较时, j和k不断自增，总有一个先到达末端 for (int i = 0; i < str1.length(); i++) {//枚举str2 先到末端 str1[i]和str2.back对应 m_dp[i][str2.length() - 1] = (str1[i] == str2.back()); for (int j = i-1 ; j >= 0 ; j-- ) { const int k = str2.length() - 1 - (i-j); if (k < 0) { break; } if (str1[j] == str2[k]) { m_dp[j][k] = 1 + m_dp[j + 1][k + 1]; } } } for (int i = 0; i < str2.length(); i++) {//枚举str1 先到末端 str2[i]和str1.back对应 m_dp[str1.length()-1][i] = (str1.back() == str2[i]); for (int j = i - 1; j >= 0; j--) { const int k = str1.length() - 1 - (i-j); if (k < 0) { break; } if (str1[k] == str2[j]) { m_dp[k][j] = 1 + m_dp[k + 1][j + 1]; } } } } vector<vector<int>> m_dp; }; class Solution { public: string findTheString(vector<vector<int>>& lcp) { const int n = lcp.size(); string word(n, ' '); for (int i = 0; ; i++) { int iPos = word.find(' '); if (-1 == iPos) { break; } if (i >= 26) { return ""; } for (int j = iPos ; j < n; j++) { if (lcp[iPos][j] >= 1) { word[j] = 'a' + i; } } } CLCP lcpHlp(word, word); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (lcp[i][j] != lcpHlp.m_dp[i][j]) { return ""; } } } return word; } };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<vector<int>> lcp; { Solution sln; lcp = { {4,0,2,0},{0,3,0,1},{2,0,2,0},{0,1,0,1} }; auto res = sln.findTheString(lcp); Assert(res,"abab"); } { Solution sln; lcp = { {4,3,2,1},{3,3,2,1},{2,2,2,1},{1,1,1,1} }; auto res = sln.findTheString(lcp); Assert(res, "aaaa"); } { Solution sln; lcp = { {4,3,2,1},{3,3,2,1},{2,2,2,1},{1,1,1,3} }; auto res = sln.findTheString(lcp); Assert(res, ""); } }
2023 年5月
class Solution {
public:
string findTheString(vector<vector>& lcp) {
char ch = ‘a’;
m_c = lcp.size();
string str(m_c, ‘#’);
for (int i = 0; i < m_c; i++)
{
if (‘#’ != str[i])
{
continue;
}
if (ch > ‘z’)
{
return “”;
}
for (int j = 0; j < m_c; j++)
{
if (lcp[i][j] > 0)
{
if (‘#’ != str[j])
{
return “”;
}
str[j] = ch;
}
}
ch++;
}
if (!Check(str, lcp))
{
return “”;
}
return str;
}
bool Check(const string& str, vector<vector>& lcp)
{
for (int r = m_c - 1; r >= 0; r–)
{
int iNum = 0;
for (int j = m_c-1,i = r ; (i>=0) && (j>=0) ; j–,i–)
{
if (str[i] == str[j])
{
iNum++;
}
else
{
iNum = 0;
}
if (lcp[i][j] != iNum)
{
return false;
}
if (lcp[i][j] != lcp[j][i])
{
return false;
}
}
}
return true;
}
int m_c;
};
