Created
June 5, 2018 00:47
-
-
Save amraks/a66ef2a1c1543c693eec22e2d00dd6e9 to your computer and use it in GitHub Desktop.
All anagrams indices of pattern in a string
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package code; | |
import java.util.ArrayList; | |
import java.util.HashMap; | |
import java.util.List; | |
import java.util.Map; | |
public class Main { | |
public static Map<Character, Integer> getCharacterFrequency(String s) { | |
Map<Character, Integer> m = new HashMap<Character, Integer>(); | |
for (int i = 0; i < s.length(); i++) { | |
if (m.containsKey(s.charAt(i))) { | |
m.put(s.charAt(i), m.get(s.charAt(i)) + 1); | |
} else { | |
m.put(s.charAt(i), 1); | |
} | |
} | |
return m; | |
} | |
public static List<Integer> getAnagramIndices(String s, String p) { | |
List<Integer> l = new ArrayList<>(); // result array | |
if (p.length() > s.length()) { | |
return l; | |
} | |
String current = ""; | |
// create initial window | |
for (int i = 0; i < p.length(); i++) { | |
current = current.concat(String.valueOf(s.charAt(i))); | |
} | |
Map<Character, Integer> currentWindowMap = getCharacterFrequency(current); // sliding window map | |
Map<Character, Integer> patternMap = getCharacterFrequency(p); // input pattern map | |
int i = p.length(); | |
do { | |
if (currentWindowMap.equals(patternMap)) { | |
l.add(i - p.length()); | |
} | |
// character at beginning of sliding window | |
char c = s.charAt(i - p.length()); | |
// reduce count of window's beginning character | |
currentWindowMap.put(c, currentWindowMap.get(c) - 1); | |
if (currentWindowMap.containsKey(c) && currentWindowMap.get(c) == 0) { | |
// remove char from map if it's count becomes 0 | |
currentWindowMap.remove(c); | |
} | |
// slide the window | |
if (currentWindowMap.containsKey(s.charAt(i))) { | |
currentWindowMap.put(s.charAt(i), currentWindowMap.get(s.charAt(i)) + 1); | |
} else { | |
currentWindowMap.put(s.charAt(i), 1); | |
} | |
i += 1; | |
} while (i < s.length()); | |
if (currentWindowMap.equals(patternMap)) { | |
l.add(i-p.length()); | |
} | |
return l; | |
} | |
public static void main(String[] args) { | |
// eg. 1 | |
System.out.println("eg. 1"); | |
for (int i : getAnagramIndices("hello", "lol")) { | |
System.out.println(i); | |
} | |
; | |
System.out.println("eg. 2"); | |
// eg. 2 | |
for (int i : getAnagramIndices("msississsippi", "siss")) { | |
System.out.println(i); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment