作者推荐
【广度优先搜索】【网格】【割点】【 推荐】1263. 推箱子
本文涉及知识点
LeetCode1147段式回文
你会得到一个字符串 text 。你应该把它分成 k 个子字符串 (subtext1, subtext2，…， subtextk) ，要求满足:
subtexti 是 非空 字符串
所有子字符串的连接等于 text ( 即subtext1 + subtext2 + … + subtextk == text )
对于所有 i 的有效值( 即 1 <= i <= k ) ，subtexti == subtextk - i + 1 均成立
返回k可能最大值。
示例 1：
输入：text = “ghiabcdefhelloadamhelloabcdefghi”
输出：7
解释：我们可以把字符串拆分成 “(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)”。
示例 2：
输入：text = “merchant”
输出：1
解释：我们可以把字符串拆分成 “(merchant)”。
示例 3：
输入：text = “antaprezatepzapreanta”
输出：11
解释：我们可以把字符串拆分成 “(a)(nt)(a)(pre)(za)(tep)(za)(pre)(a)(nt)(a)”。
提示：
1 <= text.length <= 1000
text 仅由小写英文字符组成
动态规划
动态规划的状态
n = text.length。
dp[i] 表示text[0,i)和对称部分最多可以划分几个相等的子串。
halfLen = n/2
i的取值范围[0,halfLen ]
动态规划的转移方程：
d[[i]M a x S e l f j = 0 i − 1 MaxSelf\Large_{j=0}^{i-1 }MaxSelfj=0i−1 if text[j,i) == text[j,i) 且(dp[j] > 0 或0==j)对称部分 dp[j]+2
可以枚举j，计算i。不合法的j，就忽略,速度小幅提升。
时间复杂度:**O(nn) 主要时间用在预处理最长公共前缀上。
动态规划的初始值
全为0
动态规划的填表顺序
i从1到大处理。
返回值
除n为偶数是dp.back外，全部+1。返回dp[0]
预处理
O(nn)的时间处理好最长公共前缀，方便比较
代码
核心代码
//最长公共前缀(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: int longestDecomposition(string text) { const int half = text.length() / 2; CLCP lcp(text, text); vector<int> dp(half + 1); for (int i = 1; i <= half; i++) { for (int j = 0; j < i; j++) { const int len = i - j; const int r = text.length() - 1 - j -( len - 1); if ((lcp.m_dp[j][r] >= len) &&((dp[j]>0)||(0==j))) { dp[i] = max(dp[i], dp[j] + 2); } } } if (0 == text.length() % 2) { dp.back() -= 1; } return 1 + *std::max_element(dp.begin(),dp.end()); } };
测试用例
template<class T> void Assert(const T& t1, const T& 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() { string text ; { Solution sln; text = "antaprezatepzapreanta"; auto res = sln.longestDecomposition(text); Assert(11, res); } { Solution sln; text = "aa"; auto res = sln.longestDecomposition(text); Assert(2, res); } { Solution sln; text = "aba"; auto res = sln.longestDecomposition(text); Assert(3, res); } { Solution sln; text = "ab"; auto res = sln.longestDecomposition(text); Assert(1, res); } { Solution sln; text = "merchant"; auto res = sln.longestDecomposition(text); Assert(1, res); } { Solution sln; text = "ghiabcdefhelloadamhelloabcdefghi"; auto res = sln.longestDecomposition(text); Assert(7, res); } { Solution sln; text = "elvtoelvto"; auto res = sln.longestDecomposition(text); Assert(2, res); } }
2023年一月版
class Solution {
public:
int longestDecomposition(string text) {
m_c = text.length();
for (int len = 1; len <= m_c / 2; len++)
{
if (text.substr(0, len) == text.substr(m_c - len, len))
{
return 2 + longestDecomposition(text.substr(len, m_c - len * 2));
}
}
return (“” == text) ? 0 : 1;
}
int m_c;
};
2023年8月版
class Solution {
public:
int longestDecomposition(string text) {
int iRet = 0;
int left = 0, r = text.length() - 1;
while (left < r)
{
int lcur = left, rcur = r;
while (lcur < rcur)
{
if (Is(lcur, rcur, left, r, text))
{
iRet += 2;
break;
}
lcur++;
rcur–;
}
if (lcur >= rcur)
{
return iRet + (left <= r );
}
left = lcur + 1;
r = rcur - 1;
}
return iRet + (left <= r);
}
bool Is(const int& lcur, const int& rcur, const int& left, const int r, const string& text)
{
for (int i = 0; i < lcur -left + 1; i++)
{
if (text[left + i] != text[rcur + i])
{
return false;
}
}
return true;
}
};
