作者推薦

視頻算法專題

涉及知識點

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

LeetCode10:正則表達式匹配

給你一個字符串 s 和一個字符規(guī)律 p，請你來實現(xiàn)一個支持 ‘.’ 和 ‘’ 的正則表達式匹配。
‘.’ 匹配任意單個字符
'’ 匹配零個或多個前面的那一個元素
所謂匹配，是要涵蓋 整個 字符串 s的，而不是部分字符串。
示例 1：
輸入：s = “aa”, p = “a”
輸出：false
解釋：“a” 無法匹配 “aa” 整個字符串。
示例 2:
輸入：s = “aa”, p = “a*”
輸出：true
解釋：因為 ‘’ 代表可以匹配零個或多個前面的那一個元素, 在這里前面的元素就是 ‘a(chǎn)’。因此，字符串 “aa” 可被視為 ‘a(chǎn)’ 重復(fù)了一次。
示例 3：
輸入：s = “ab”, p = "."
輸出：true
解釋："." 表示可匹配零個或多個（'’）任意字符（‘.’）。
提示：
1 <= s.length <= 20
1 <= p.length <= 20
s 只包含從 a-z 的小寫字母。
p 只包含從 a-z 的小寫字母，以及字符 . 和 *。
保證每次出現(xiàn)字符 * 時，前面都匹配到有效的字符

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

時間復(fù)雜度??(nnm) n=s.length m = p.length

滾動哈希集合

轉(zhuǎn)移狀態(tài)時：只需要讀取j1的相關(guān)狀態(tài)，寫人j1+1的狀態(tài)。我們用兩個哈希來表示狀態(tài)：pre表示j1 相關(guān)狀態(tài),dp 表示j2的相關(guān)狀態(tài)，然后swap。

分類討論

代碼

核心代碼

class Solution {
public:
	bool isMatch(string s, string p) {
		m_c = s.length();
		unordered_set<int> pre = { 0 };
		for (int i = 0 ; i < p.length(); i++ )
		{	
			const auto& ch = p[i];
			if ('*' == ch)
			{
				continue;
			}
			unordered_set<int> dp;
			if ((i + 1 < p.length()) && ('*' == p[i + 1]))
			{
				if ('.' == ch)
				{
					int iMin = INT_MAX;
					for (const auto& iPre : pre)
					{
						iMin = min(iMin, iPre);
					}
					for (; iMin <= m_c; iMin++)
					{
						dp.insert(iMin);
					}
				}
				else
				{
					dp = pre;
					for (const auto& iPre : pre)
					{
						int j = iPre;
						while (j < m_c)
						{
							if (s[j] == ch)
							{
								dp.insert(++j);
							}
							else
							{
								break;
							}
						}
					}
				}
			}
			else
			{
				for (const auto& iPre : pre)
				{
					if (iPre  < m_c)
					{
						if (('.' == ch) || (s[iPre] == ch))
						{
							dp.insert(iPre + 1);
						}
					}
				}
			}			
			pre.swap(dp);
		}
		return pre.count(m_c);
	}
	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 s, p;

	{
		Solution sln;
		s = "aa", p = "a";
		auto res = sln.isMatch(s, p);
		Assert(false, res);
	}
	{
		Solution sln;
		s = "aa", p = "aa";
		auto res = sln.isMatch(s, p);
		Assert(true, res);
	}
	{
		Solution sln;
		s = "a", p = "a*";
		auto res = sln.isMatch(s, p);
		Assert(true, res);
	}
	{
		Solution sln;
		s = "aa", p = "a*";
		auto res = sln.isMatch(s, p);
			Assert(true, res);
	}
	{
		Solution sln;
		s = "aaa", p = "a*";
		auto res = sln.isMatch(s, p);
		Assert(true, res);
	}
	{
		Solution sln;
		s = "ab", p = ".*";
		auto res = sln.isMatch(s, p);
		Assert(true, res);
	}
	{
		Solution sln;
		s = "aab", p = "c*a*b";
		auto res = sln.isMatch(s, p);
		Assert(true, res);
	}
	{
		Solution sln;
		s = "aaaaaaaaaaaaab", p = "a*a*a*a*a*a*a*a*a*a*";
		auto res = sln.isMatch(s, p);
		Assert(false, res);
	}
}

動態(tài)規(guī)劃的優(yōu)化

時間復(fù)雜度??(nm)
優(yōu)化動態(tài)規(guī)劃的轉(zhuǎn)移方程，改成枚舉s。也要處理匹配多個的問題。比如：連續(xù)多個不匹配任何字符。
不用滾動哈希集合了。

如果p[i-1]是星號，只需要考慮兩種情況：

• 匹配0個字符,dp[i][j] = dp[i-2][j]。
• 匹配n個字符，n>0。 dp[i][j] = dp[i][j-1]

注意
dp[0][x] x>0，無意義全部為false。
dp[x][0] x>0 如果p[0,x)全部是yyyy… ，則為true。 y表示.或字母，兩個y可能不相同。
y* 必須處理號，不能處理y，否則如果以號結(jié)束的時候，會出錯。

動態(tài)規(guī)劃的無后效性

計算dp[i][j]的時候，用到了i,i-1,i-2,j,j-1。 第一層循環(huán)從小到大枚舉i，第二層循環(huán)從小到大枚舉j。i小的先處理，i相等的,j小的先處理。

代碼

class Solution {
public:
	bool isMatch(string s, string p) {
		m_r = p.length();
		m_c = s.length();
		vector<vector<bool>> dp(m_r+1, vector<bool>(m_c+1));
		dp[0][0] = true; 
		for (int i = 1; (i < m_r)&&('*'== p[i]); i+=2 )
		{
			dp[i + 1][0] = dp[i - 1][0];
		}
		for (int i = 1; i <= m_r; i++)
		{
			auto Match = [&p, &s](int i,int j) {return ('.' == p[i]) || (s[j] == p[i]); };
			if ((i < m_r) && ('*' == p[i]))
			{
				continue;//x* 在*號那處理
			}
			for (int j = 1; j <= m_c; j++)
			{	
				if ('*' == p[i-1])
				{
					if (i >= 2)
					{//匹配0個字符
						dp[i][j] = dp[i][j] | dp[i - 2][j];
					}
					if (!Match(i - 2, j-1))
					{
						continue;
					}
					dp[i][j] = dp[i][j] | dp[i][j-1];//dp[i][j-1] 的*號，可能匹配了0次，1次,2次...
				}
				else
				{
					if (!Match(i-1, j-1))
					{
						continue;
					}
					dp[i][j] = dp[i - 1][j - 1];
				}
			}

		}
		return dp[m_r][m_c];
	}
	int m_r, m_c;
};

2022年12月舊版

class Solution {
public:
bool isMatch(string s, string p) {
const int lenS = s.size();
const int lenP = p.size();
//dp[i][j]表示 p的前i個字符能否和s的前j個字符匹配
vector<vector> dp;
dp.assign(lenP + 1, vector(lenS + 1));
dp[0][0] = true;
for (int i = 1; i <= lenP; i++)
{
for (int j = 0; j <= lenS; j++)
{
if (‘’ == p[i-1])
{
if (dp[i -2][j ])
{//匹配0個字符
dp[i ][j ] = true;
}
if (0 == j)
{
continue;
}
if (IsSame(p[i - 2], s[j-1]))
{
//匹配一次和匹配多次
if (dp[i - 2][j] || dp[i ][j-1])
{
dp[i][j] = true;
}
}
}
if (0 == j)
{
continue;
}
if ((i < lenP) && ('’ == p[i ]))
{
//dp[i + 1 + 1][j + 1] != dp[i][j];
}
else
{
if (IsSame(p[i-1], s[j-1]) && dp[i-1][j-1] )
{
dp[i][j] = true;
}
}
}
}
return dp[lenP][lenS];
}
bool IsSame(const char& ch1, const char& ch2)
{
return (‘.’ == ch1) || (‘.’ == ch2) | (ch1 == ch2);
}
};

擴展閱讀

視頻課程

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

如何你想快

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

相關(guān)下載

想高屋建瓴的學(xué)習(xí)算法，請下載《喜缺全書算法冊》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-771371.html

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