leetocde 567. Permutation in String

leetocde 567. Permutation in String

题意：给你两个字符串s1,s2，是否在s2中存在s1的全排列。

思路：统计s1各个数字的总数，然后在s2每个位置和s1比较。

代码1：O(26*n)

class Solution {
public:bool checkInclusion(string s1, string s2) {int l1 = s1.length();int l2 = s2.length();vector<int> num(30, 0);for (int i = 0; i < l1; i++)num[s1[i] - 'a']++;vector<vector<int>> dp(10005, vector<int>(30, 0));for (int i = 0; i < l2; i++){if (i == 0){dp[i+1][s2[i] - 'a']++;}else{dp[i+1] = dp[i];dp[i+1][s2[i] - 'a']++;}}for (int i = l2; i >= 1 && i - l1 >= 0; i--){int flag = 1;for (int j = 0; j < 26; j++){if (dp[i][j] - dp[i - l1][j] != num[j]){flag = 0;break;}}if (flag == 1)	return true;}return false;}
}

代码2：O(n)

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