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是否是同一个串的不同排列。 代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时1365MS。 优化方法是使用滑动窗口方法，假设s1的长度为n。先hash s1，再在s2中开长度为n的窗口，判断窗口内的子串hash是否和s1的hash相等，相等则返回tru，否则窗口向右滑动一格，即增加右边一个字符频率，同时减掉左边一个字符频率，如此循环。 代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时13MS。]]>