给定两个字符串 s1
和 s2
,写一个函数来判断 s2
是否包含 s1
的排列。
换句话说,第一个字符串的排列之一是第二个字符串的 子串 。
示例 1:
输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba").
示例 2:
输入: s1= "ab" s2 = "eidboaoo" 输出: False
提示:
- 输入的字符串只包含小写字母
- 两个字符串的长度都在
[1, 10,000]
之间
class Solution { public: bool checkInclusion(string s1, string s2) { unordered_map<char,int> need_map, window_map; for(auto c : s1) { need_map[c]++; } int left = 0; int right = 0; int valid = 0; while(right < s2.size()) { char cur_c = s2[right]; if (need_map.find(cur_c) != need_map.end()) { window_map[cur_c]++; if(need_map[cur_c] == window_map[cur_c]) { valid++; } } right++; cout << left << " " << right << endl; while(right-left>=s1.size()) { //本题移动 left 缩小窗口的时机是窗口大小大于 t.size() 时,应为排列嘛,显然长度应该是一样的。 if(valid == need_map.size()) return true; //当发现 valid == need.size() 时,就说明窗口中就是一个合法的排列,所以立即返回 true。 char cur_c = s2[left]; if(need_map.find(cur_c) != need_map.end()) { if(need_map[cur_c] == window_map[cur_c]) { valid--; } window_map[cur_c]--; } left++; } } return false; } };