Merge pull request AlgoStudyGroup#110 from kerms/patch-2

jinshendan · web-flow · commit 29641c85e86f · 2020-05-18T17:03:55.000+02:00
[May 18, 2020] Add cpp solution2
diff --git a/May-LeetCoding-Challenge/18-Permutation-In-String/Permutation-In-String.cpp b/May-LeetCoding-Challenge/18-Permutation-In-String/Permutation-In-String.cpp
@@ -30,4 +30,30 @@ class Solution {
         
         return false; 
     }
-};
+};
+
+class Solution2 {
+public:
+    bool checkInclusion(string s1, string s2) {
+        vector<int> h1(26,0);
+        int count = s1.size();
+        int right = 0, left = 0;
+        int l_idx;
+        
+        for (char &c : s1) ++h1[c-'a'];
+        
+        for (int right = 0; right < s2.size() ; ++right) {
+            count -= h1[s2[right]-'a']-- > 0;
+            if (count == 0) {
+                l_idx = right - s1.size() + 1;
+                for (; left < l_idx; ++left)
+                    count += h1[s2[left]-'a']++ >= 0;
+
+                if (count == 0)
+                    return true;
+            }
+        }
+        
+        return false;
+    }
+};
