A different sliding window approach using binary marker


  • 0

    Since there are only 26 lower case letters, I use 32-bit int as a marker to mark the int[26] array's difference.
    If it's different, set that bit to 1, 0 otherwise.
    If marker equals 0, the substring is the one.

        /**
         * 
         * @param s base
         * @param p pattern
         * @return
         */
        public static List<Integer> findAnagrams(String s, String p) {
        	List<Integer> table = new LinkedList<Integer>();
        	if(s.length() < p.length())	return table;
    		int mark = 0;
    		int[] base = new int[26];
    		int[] window = new int[26];
    		int length = p.length();
    		
    		
    		//initialize mark and base and window
    		for(int i = 0; i < length; i++){
    			base[p.charAt(i) - 'a']++;
    			window[s.charAt(i) - 'a']++;
    		}
    		
    		//check two window differences
    		for(int i = 0; i < 26; i++){
    			if(base[i] != window[i]){
    				//mark the difference in mark, bit by bit
    				mark |= 1 << i;
    			}
    		}
    		
    		//the starting String is the same
    		if(mark == 0){
    			table.add(0);
    		}
    		
    		for(int i = length; i < s.length(); i++){
    			//erase the one before new string, add the last new byte in the new string
    			int oldHead = s.charAt(i - length) - 'a';
    			int newTail = s.charAt(i) - 'a';
    			window[oldHead]--;
    			window[newTail]++;
    			
    			//recalculate the mark
    			if(base[oldHead] == window[oldHead]){
    				mark &= ~(1 << oldHead);//if equal, reset to 0
    			}
    			else{
    				mark |= 1 << oldHead; //if not equal, set to 1
    			}
    			if(base[newTail] == window[newTail]){
    				mark &= ~(1 << newTail);
    			}
    			else{
    				mark |= 1 << newTail;
    			}
    			
    			if(mark == 0){
    				table.add(i - length + 1);
    			}
    		}
    		
    		return table;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.