Merge pull request AlgoStudyGroup#105 from qilingit/day17

jinshendan · web-flow · commit 0648bda913f1 · 2020-05-17T23:11:52.000+02:00
Add java sliding window solution for day17: Find All Anagrams in a String
diff --git a/May-LeetCoding-Challenge/17-Find-All-Anagrams-In-A-String/Find-All-Anagrams-In-A-String.java b/May-LeetCoding-Challenge/17-Find-All-Anagrams-In-A-String/Find-All-Anagrams-In-A-String.java
@@ -67,6 +67,39 @@ public List<Integer> findAnagrams(String s, String p) {
              if(isAnagram(subString, p)) res.add(i);
         }
         
+        return res;
+    }
+}
+
+// Sliding windows solution
+class Solution3 {
+    private boolean checkDiff(int[] diff){
+        for (int i = 0; i < diff.length; i++) 
+            if (diff[i] != 0) return false;
+        
+        return true;
+    }
+    
+    public List<Integer> findAnagrams(String s, String p) {
+        List<Integer> res = new ArrayList<>();
+        int sLength = s.length(), pLength = p.length();
+        if(sLength < pLength || s == null) return res;
+        
+        int[] diff = new int[26];
+        
+        for(int i = 0; i < pLength; i++) {
+            diff[p.charAt(i) - 'a']--;
+            diff[s.charAt(i) - 'a']++;
+        }
+        if(checkDiff(diff)) res.add(0);
+        
+        //sliding window
+        for (int i = pLength; i < sLength; i++) {
+            diff[s.charAt(i) - 'a']++;
+            diff[s.charAt(i - pLength) - 'a']--;
+            if(checkDiff(diff)) res.add(i - pLength + 1);
+        }
+        
         return res;
     }
 }
