判断字符串是否包含另一字符串的全排列

时间：2025-02-15 18:02:33

问题I：
给定两个字符串A和B，判断A中是否包含由B中字符重新排列成的新字符串。例如：A=abcdef, B=ba，结果应该返回true。因为ba的排列ab，是A的子串。本问题来自：微信公众账号“待字闺中”。


分析：

设A的长度为n，B的长度为m

很直观的做法是：

1）先分析B中的字符有有哪些，每种字符出现了多少次。

2）遍历A中每个长度为m的子串，统计字符，然后与B的统计结果对照。

这种解法虽然时间复杂度是O（2*n+m），但要做统计的对照，所以时间复杂度还与字符种类有关。若只有26个小写字母，时间复杂度就是O（26*2n+m）。


实际上，这个系数可以优化掉：

用一个整数N表示B中字符的种类数；用整数M表示，在长度为m的子串中出现次数不少于在B中出现次数的字符的种数。

遍历A中每个长度为m的子串时，当前子串的统计结果，只是在上一次统计结果的基础上添加和去掉一个元素。

去掉一个字符ch，若去掉前，ch出现的次数正好等于在B中出现的次数，那么--M。

添加一个字符ch，若添加后，ch出现的次数正好等于在B中出现的次数，那么++M。

若M == N，那么就在A中找到了一个B的全排列子串。

这样，不论字符的总类有多少，时间复杂度总是O（2n+m）。

C++实现：

bool contin(const string &A, const string &B){
	if(() < ())
		return false;
	if(() == true)
		return true;
	unordered_map<char, int> aMap, bMap;
	for(char ch : B)
		++bMap[ch];
	int kindCount = ();
	int loc = 0;
	int okCount = 0;
	while(okCount < kindCount && loc < ()){
		if(loc >= ()){
			int preHead = loc - ();
			int tmp = aMap[A[preHead]]--;
			auto it = (A[preHead]);
			if(it != () && tmp == it->second)
				--okCount;
		}
		int tmp = ++aMap[A[loc]];
		auto it = (A[loc]);
		if(it != () && tmp == it->second)
			++okCount;
		++loc;
	}
	return okCount == kindCount;
}



问题II：

将问题I变形一下，求A中最短的包含了B中所有字符的子串。

这其实是LeetCode上的一道题：Minimum Window Substring 

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

问题II的解法跟问题I很相似，就不再分析了，直接上代码：

C++实现：时间复杂度同问题I

string minWindow(string A, string B) {
	if(() < () || ())
		return "";
	unordered_map<char, int> aMap, bMap;
	for(char ch : B)
		++bMap[ch];
	int kindCount = ();
	int okCount = 0;
	int s = 0, t = 0;
	int minLen = INT_MAX;
	int resS = 0, resT = 0;
	while(t < ()){
		while(okCount != kindCount && t < ()){
			int tmp = ++aMap[A[t]];
			auto it = (A[t]);
			if(it != () && tmp == it->second)
				++okCount;
			++t;
		}
		while(okCount == kindCount){
			if(t - s < minLen){
				minLen = t - s;
				resS = s, resT = t;
			}
			int tmp = aMap[A[s]]--;
			auto it = (A[s]);
			if(it != () && tmp == it->second)
				--okCount;
			++s;
		}
	}
	return minLen == INT_MAX ? "" : (resS, resT - resS);
}




相关文章