LeetCode Permutation in String

LeetCode Permutation in String

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:

  1. The input strings only contain lower case letters.
  2. The length of both given strings is in range [1, 10,000].

给定两个字符串s1和s2,问s1的排列是否是s2的子串。

暴力方法是枚举s2的每个字符,如果在s1中,则在s2中取等长的子串,hash判断s2的子串和s1是否是同一个串的不同排列。

代码如下:

class Solution {
public:
	bool checkInclusion(string s1, string s2) {
		int n = s1.size(), m = s2.size();
		if (n > m)return false;
		unordered_map<char, int> hash1;
		for (int i = 0; i < n; ++i)++hash1[s1[i]];
		for (int i = 0; i < m; ++i) {
			if (hash1.find(s2[i]) != hash1.end()) {
				if (i + n <= m) {
					unordered_map<char, int> hash2;
					for (int j = i; j < i + n; ++j)++hash2[s2[j]];
					if (hash1 == hash2)return true;
				}
			}
		}
		return false;
	}
};

本代码提交AC,用时1365MS。

优化方法是使用滑动窗口方法,假设s1的长度为n。先hash s1,再在s2中开长度为n的窗口,判断窗口内的子串hash是否和s1的hash相等,相等则返回tru,否则窗口向右滑动一格,即增加右边一个字符频率,同时减掉左边一个字符频率,如此循环。

代码如下:

class Solution {
public:
	bool checkInclusion(string s1, string s2) {
		int n = s1.size(), m = s2.size();
		if (n > m)return false;
		vector<int> hash1(26, 0), hash2(26, 0);
		for (int i = 0; i < n; ++i) {
			++hash1[s1[i] - 'a'];
			++hash2[s2[i] - 'a'];
		}
		if (hash1 == hash2)return true;
		for (int i = n; i < m; ++i) {
			++hash2[s2[i] - 'a'];
			--hash2[s2[i - n] - 'a'];
			if (hash1 == hash2)return true;
		}
		return false;
	}
};

本代码提交AC,用时13MS。

Leave a Reply

Your email address will not be published. Required fields are marked *