作者推薦

視頻算法專題

本文涉及知識(shí)點(diǎn)

動(dòng)態(tài)規(guī)劃匯總
字符串

LeetCode132. 分割回文串 II

給你一個(gè)字符串 s，請(qǐng)你將 s 分割成一些子串，使每個(gè)子串都是回文。
返回符合要求的 最少分割次數(shù) 。
示例 1：
輸入：s = “aab”
輸出：1
解釋：只需一次分割就可將 s 分割成 [“aa”,“b”] 這樣兩個(gè)回文子串。
示例 2：
輸入：s = “a”
輸出：0
示例 3：
輸入：s = “ab”
輸出：1
提示：
1 <= s.length <= 2000
s 僅由小寫英文字母組成

動(dòng)態(tài)規(guī)劃

分兩步：
一，枚舉回文的中心，記錄所有的回文。空間復(fù)雜度和時(shí)間復(fù)雜度都是O(nn)。
二，通過(guò)動(dòng)態(tài)規(guī)劃計(jì)算所有所有前綴可以差分成多少個(gè)不重疊的子字符串?？臻g復(fù)雜度O(n)，時(shí)間復(fù)雜度是O(nn)。

變量解析

態(tài)規(guī)范分析

代碼

核心代碼

class Solution {
public:
	int minCut(string s) {
		m_c = s.length();
		vector<vector<int>> vRightToLeft(m_c);//cRightToLeft[i] 包括元素j，表示s[i,j]，是回文串。
		for (int i = 0; i < m_c; i++)
		{
			for (int left = i, right = i; (left >= 0) && (right < m_c)&&(s[left]==s[right]); left--, right++)
			{//奇數(shù)長(zhǎng)度回文
				vRightToLeft[right].emplace_back(left);
			}
			for (int left = i, right = i+1; (left >= 0) && (right < m_c) && (s[left] == s[right]); left--, right++)
			{//偶數(shù)長(zhǎng)度回文
				vRightToLeft[right].emplace_back(left);
			}
		}
		vector<int> dp(m_c,INT_MAX);
		for (int i = 0; i < m_c; i++)
		{
			for (const auto& left : vRightToLeft[i])
			{
				dp[i] = min(dp[i], 1 + (left > 0 ? dp[left - 1] : 0));
			}
		}
		return dp.back()-1;
	}
	int m_c;
};

測(cè)試用例

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 s;	
	{
		Solution sln;
		s = "aab";
		auto res = sln.minCut(s);
		Assert(1, res);
	}
	{
		Solution sln;
		s = "a";
		auto res = sln.minCut(s);
		Assert(0, res);
	}
	{
		Solution sln;
		s = "ab";
		auto res = sln.minCut(s);
		Assert(1, res);
	}
}

2023年1月版

class Solution {
public:
int minCut(string s) {
m_c = s.length();
vector<vector> is;
is.assign(m_c, vector(m_c+1));
for (int c = 0; c < m_c; c++)
{
//長(zhǎng)度為1的字符串一定是回文
is[c][1] = true;
}
for (int c = 0; c + 1 < m_c; c++)
{
is[c][2] = (s[c] == s[c + 1]);
}
for (int len = 3; len <= m_c; len++)
{
for (int c = 0; c + len - 1 < m_c; c++)
{
is[c][len] = is[c + 1][len - 2] && (s[c] == s[c + len - 1]);
}
}
//最少多少個(gè)回文構(gòu)成
vector dp(m_c + 1,INT_MAX);
dp[0] = 0;
for (int c = 0; c < m_c; c++)
{
for (int len = 1; len <= m_c; len++)
{
if (is[c][len] && (c+len <= m_c ))
{
dp[c + len] = min(dp[c + len], dp[c] + 1);
}
}
}
return dp[m_c] - 1;
}
int m_c;
};

2023年8月

//馬拉車計(jì)算回文回文
class CPalindrome
{
public:
//vOddHalfLen[i]表示 以s[i]為中心，且長(zhǎng)度為奇數(shù)的最長(zhǎng)回文的半長(zhǎng)，包括s[i]
//比如：“aba” vOddHalfLen[1]為2 “abba” vEvenHalfLen[1]為2
static void Do(vector& vOddHalfLen, vector& vEvenHalfLen,const string& s)
{
vector v;
for (const auto& ch : s)
{
v.emplace_back(ch);
v.emplace_back(‘*’);
}
v.pop_back();
const int len = v.size();
vector vHalfLen(len);
int center = -1, r = -1;
//center是對(duì)稱中心,r是其右邊界（閉）
for (int i = 0; i < len; i++)
{
int tmp = 1;
if (i <= r)
{
int pre = center - (i - center);
tmp = min(vHalfLen[pre], r - i + 1);
}
for (tmp++; (i + tmp - 1 < len) && (i - tmp + 1 >= 0) && (v[i + tmp - 1] == v[i - tmp + 1]); tmp++);
vHalfLen[i] = --tmp;
const int iNewR = i + tmp - 1;
if (iNewR > r)
{
r = iNewR;
center = i;
}
}
vOddHalfLen.resize(s.length());
vEvenHalfLen.resize(s.length());
for (int i = 0; i < len; i++)
{
if (i & 1)
{
vEvenHalfLen[i / 2] = vHalfLen[i] / 2;

		}
		else
		{
			vOddHalfLen[i / 2] = (vHalfLen[i]+1) / 2 ;				
		}
	}
}

};
class Solution {
public:
int minCut(string s) {
m_c = s.length();
vector vOddHalfLen, vEvenHalfLen;
CPalindrome::Do(vOddHalfLen, vEvenHalfLen,s);
//鄰接表
vector<vector> vNeiBo(m_c+1);
for (int i = 0; i < m_c; i++)
{
for (int len = 1; len <= vOddHalfLen[i]; len++)
{
const int cur = i - len + 1;
const int next = i + len;
vNeiBo[cur].emplace_back(next);
}
for (int len = 1; len <= vEvenHalfLen[i]; len++)
{
const int cur = i - len + 1;
const int next = i + len+1;
vNeiBo[cur].emplace_back(next);
}
}
queue que;
que.emplace(0);
vector vDis(m_c+1, -1);
vDis[0] = 0;
while (que.size())
{
const int cur = que.front();
que.pop();
const int curDis = vDis[cur];
for (const auto& next : vNeiBo[cur])
{
if (-1 != vDis[next])
{
continue;
}
vDis[next] = curDis + 1;
que.emplace(next);
}
}
return vDis.back() - 1;
}
int m_c;
};

擴(kuò)展閱讀

視頻課程

有效學(xué)習(xí)：明確的目標(biāo) 及時(shí)的反饋 拉伸區(qū)（難度合適），可以先學(xué)簡(jiǎn)單的課程，請(qǐng)移步CSDN學(xué)院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成戰(zhàn)斗了，為老板分憂，請(qǐng)學(xué)習(xí)C#入職培訓(xùn)、C++入職培訓(xùn)等課程
https://edu.csdn.net/lecturer/6176

相關(guān)下載

想高屋建瓴的學(xué)習(xí)算法，請(qǐng)下載《喜缺全書算法冊(cè)》doc版
https://download.csdn.net/download/he_zhidan/88348653

測(cè)試環(huán)境

操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開發(fā)環(huán)境： VS2022 C++17
如無(wú)特殊說(shuō)明，本算法用**C++**實(shí)現(xiàn)。

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-779368.html

到了這里，關(guān)于【動(dòng)態(tài)規(guī)劃】【字符串】132.分割回文串 II的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！