-
-
Save LoneRan/f696afb961895af1f93e75764fa0122a to your computer and use it in GitHub Desktop.
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
import java.util.*; | |
public class solution_medium_438 { | |
public List<Integer> findAnagrams(String s, String p) { | |
//init a collection or int value to save the result according the question. | |
List<Integer> result = new LinkedList<>(); | |
if(p.length()> s.length()) return result; | |
Map<Character, Integer> map = new HashMap<>(); | |
for(char c : p.toCharArray()){ | |
map.put(c, map.getOrDefault(c, 0) + 1); | |
} | |
//maintain a counter to check whether match the target string. | |
int counter = map.size();//must be the map size, NOT the string size because the char may be duplicate. | |
//Two Pointers: begin - left pointer of the window; end - right pointer of the window | |
int begin = 0, end = 0; | |
//the length of the substring which match the target string. | |
int len = Integer.MAX_VALUE; | |
//loop at the begining of the source string | |
while(end < s.length()){ | |
char c = s.charAt(end);//get a character | |
if( map.containsKey(c) ){ | |
map.put(c, map.get(c)-1);// plus or minus one | |
if(map.get(c) == 0) counter--;//modify the counter according the requirement(different condition). | |
} | |
end++; | |
//increase begin pointer to make it invalid/valid again | |
while(counter == 0 /* counter condition. different question may have different condition */){ | |
char tempc = s.charAt(begin);//***be careful here: choose the char at begin pointer, NOT the end pointer | |
if(map.containsKey(tempc)){ | |
map.put(tempc, map.get(tempc) + 1);//plus or minus one | |
if(map.get(tempc) > 0) counter++;//modify the counter according the requirement(different condition). | |
} | |
/* save / update(min/max) the result if find a target*/ | |
// result collections or result int value | |
if(end-begin == p.length()){ | |
result.add(begin); | |
} | |
begin++; | |
} | |
} | |
return result; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment