作者推荐

【深度优先搜索】【树】【有向图】【推荐】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;
};