作者推薦

視頻算法專題

本文涉及知識點

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

LeetCode87擾亂字符串

使用下面描述的算法可以擾亂字符串 s 得到字符串 t ：
如果字符串的長度為 1 ，算法停止
如果字符串的長度 > 1 ，執(zhí)行下述步驟：
在一個隨機下標處將字符串分割成兩個非空的子字符串。即，如果已知字符串 s ，則可以將其分成兩個子字符串 x 和 y ，且滿足 s = x + y 。
隨機 決定是要「交換兩個子字符串」還是要「保持這兩個子字符串的順序不變」。即，在執(zhí)行這一步驟之后，s 可能是 s = x + y 或者 s = y + x 。
在 x 和 y 這兩個子字符串上繼續(xù)從步驟 1 開始遞歸執(zhí)行此算法。
給你兩個 長度相等 的字符串 s1 和 s2，判斷 s2 是否是 s1 的擾亂字符串。如果是，返回 true ；否則，返回 false 。
示例 1：
輸入：s1 = “great”, s2 = “rgeat”
輸出：true
解釋：s1 上可能發(fā)生的一種情形是：
“great” --> “gr/eat” // 在一個隨機下標處分割得到兩個子字符串
“gr/eat” --> “gr/eat” // 隨機決定：「保持這兩個子字符串的順序不變」
“gr/eat” --> “g/r / e/at” // 在子字符串上遞歸執(zhí)行此算法。兩個子字符串分別在隨機下標處進行一輪分割
“g/r / e/at” --> “r/g / e/at” // 隨機決定：第一組「交換兩個子字符串」，第二組「保持這兩個子字符串的順序不變」
“r/g / e/at” --> “r/g / e/ a/t” // 繼續(xù)遞歸執(zhí)行此算法，將 “at” 分割得到 “a/t”
“r/g / e/ a/t” --> “r/g / e/ a/t” // 隨機決定：「保持這兩個子字符串的順序不變」
算法終止，結(jié)果字符串和 s2 相同，都是 “rgeat”
這是一種能夠擾亂 s1 得到 s2 的情形，可以認為 s2 是 s1 的擾亂字符串，返回 true
示例 2：
輸入：s1 = “abcde”, s2 = “caebd”
輸出：false
示例 3：
輸入：s1 = “a”, s2 = “a”
輸出：true
參數(shù)：
s1.length == s2.length
1 <= s1.length <= 30
s1 和 s2 由小寫英文字母組成

動態(tài)規(guī)劃

時間復雜度??(n⁴) ，狀態(tài)數(shù)n ^ 3^,每個狀態(tài)的轉(zhuǎn)移時間復雜度O(n)。

代碼

核心代碼

template<class T>
void AssignVector3(vector<vector<vector<T>>>& v, int len1, int len2, int len3, T tDefault)
{
	v.assign(len1, vector<vector<T>>(len2, vector<T>(len3, tDefault)));
}

class Solution {
public:
	bool isScramble(string s1, string s2) {
		m_c = s1.length();
		vector < vector<vector<bool>>> dp;
		AssignVector3(dp, m_c + 1, m_c, m_c, false);
		for (int len = 1; len <= m_c; len++)
		{
			for (int i = 0; i + len <= m_c; i++)
			{
				for (int j = 0; j + len <= m_c; j++)
				{
					if (1 == len)
					{
						dp[len][i][j] = (s1[i] == s2[j]);
					}
					for (int k = 1; k < len; k++)
					{
						//交換 和 不交換
						bool b = (dp[k][i][j + len - k] && dp[len - k][i + k][j]) || (dp[k][i][j] && dp[len - k][i + k][j+k]);
						dp[len][i][j] = dp[len][i][j] || b;
					}
				}
			}
		}
		return dp[m_c][0][0];
	}
	int m_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 s1,s2;	
	{
		Solution sln;
		s1 = "great", s2 = "rgeat";
		auto res = sln.isScramble(s1, s2);
		Assert(true, res);
	}
	{
		Solution sln;
		s1 = "abcde", s2 = "caebd";
		auto res = sln.isScramble(s1, s2);
		Assert(false, res);
	}
	{
		Solution sln;
		s1 = "a", s2 = "a";
		auto res = sln.isScramble(s1, s2);
		Assert(true, res);
	}
	

}

2022年12月版

class Solution {
public:
bool isScramble(string s1, string s2) {
bool dp[31][30][30] = { false };
for (int i = 0; i < s1.length(); i++)
{
for (int j = 0; j < s2.length(); j++)
{
dp[1][i][j] = s1[i] == s2[j];
}
}
for (int len = 2; len <= s1.length(); len++)
{
for (int i = 0; i+len-1 < s1.length(); i++)
{
for (int j = 0; j + len - 1 < s2.length(); j++)
{
bool b = false;
for (int m = 1; m < len; m++)
{
if (dp[m][i][j] && dp[len - m][i + m][j + m])
{
b = true;
}
if (dp[m][i][j + len - m] && dp[len - m][i + m][j])
{
b = true;
}
}
dp[len][i][j] = b;
}
}
}
return dp[s1.length()][0][0];
}
};

2023年6月版

class Solution {
public:
bool isScramble(string s1, string s2) {
m_c = s1.length();
vector < vector<vector>> vLenBegin1Begin2(m_c + 1, vector<vector>(m_c, vector(m_c,true)));
for (int b1 = 0; b1 < m_c; b1++)
{
for (int b2 = 0; b2 < m_c; b2++)
{
vLenBegin1Begin2[1][b1][b2] = s1[b1] == s2[b2];
}
}
for (int len = 2; len <= m_c; len++)
{
for (int b1 = 0; b1 + len - 1 < m_c; b1++)
{
for (int b2 = 0; b2 + len - 1 < m_c; b2++)
{
bool bSame = false;
for (int leftLen = 1; leftLen < len; leftLen++)
{
const int iRightLen = len - leftLen;
//不改變位置
const int tmp = vLenBegin1Begin2[leftLen][b1][b2] && vLenBegin1Begin2[len - leftLen][b1 + leftLen][b2 + leftLen];
bSame |= tmp;
//改變位置
const int tmp2 = vLenBegin1Begin2[leftLen][b1][b2 + iRightLen] && vLenBegin1Begin2[iRightLen][b1 + leftLen][b2];
bSame |= tmp2;
}
vLenBegin1Begin2[len][b1][b2] = bSame;
}
}
}
return vLenBegin1Begin2.back()[0][0];
}
int m_c;
};

擴展閱讀

視頻課程

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

如何你想快

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

相關

下載

想高屋建瓴的學習算法，請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653

測試環(huán)境

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

文章來源地址http://www.zghlxwxcb.cn/news/detail-777288.html

到了這里，關于【動態(tài)規(guī)劃】【字符串】擾亂字符串的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！