idan.nik
BAN USERimport java.util.ArrayList;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Map;
public class Sol {
public static void main (String [] args){
String a= "sis";
String b = "mississippi";
ArrayList<Integer> ans = getFirstIndPerm(a,b);
System.out.println(ans);
}
private static ArrayList<Integer> getFirstIndPerm(String a, String b) {
ArrayList<Integer> ans = new ArrayList<Integer>();
HashMap<Character,Integer > charMap = new HashMap<Character,Integer > ();
HashMap<Character,Integer > checkMap = new HashMap<Character,Integer > ();
int start = -1;
int l=0;
int shortLen=a.length();
updateMap(a.toCharArray(),charMap);
for(int i=0; i< b.length();++i){
char cur = b.charAt(i);
if(!charMap.containsKey(cur))
{
l=0;
checkMap.clear();
start=-1;
continue;
}
if(charMap.get(cur)==checkMap.get(cur)){
for(int j=0;j<l;j++){
char ch= b.charAt(start+j);
checkMap.put(ch, checkMap.get(ch)-1);
l--;
if(l==0)
{
start=-1;
break;
}
if(ch==cur){
start+=j+1;
break;
}
}
}
if(start==-1)
start=i;
if(!checkMap.containsKey(cur))
checkMap.put(cur, 1);
else
checkMap.put(cur,checkMap.get(cur)+1);
l++;
if(l==shortLen){
ans.add(start);
char ch= b.charAt(start);
checkMap.put(ch, checkMap.get(ch)-1);
l--;
start++;
}
}
return ans;
}
private static void updateMap(char[] cs, HashMap<Character, Integer> charMap) {
for(char ch : cs){
if(charMap.containsKey(ch))
charMap.put(ch,charMap.get(ch)+1);
else
charMap.put(ch,1);
}
}
}
using the next class which saves the root and leaf of each flatten BST :
- idan.nik October 18, 2015