Find All Anagrams in a String

Leave a comment

November 6, 2016 by oneOokay

想来想去好多种解法 ,但是感觉都不是最优:

  1. DFS+backtracking找出p的所有的anagrams,然后遍历s看是否存在于anagrams中:但是这个如果p长度很大而且s跟p长度一样的时候,时间复杂度太大了,不值得,所以不行。
  2. 一个HashMap<Character, int>来存p,然后遍历s,对于int是否等于0进行判断。

进而:想到了:不用都对p.length()个进行处理一遍,因为每次移动都是最左边一个出去,最右边一个进来。所以想到了sliding window。我觉得好不容易啊我竟然能想到这个。然后依旧写不出来=。=

Sliding Window

Basically, we are interested only when every hash[i] becomes 0. There are a number of ways of doing it. To understand OP’s approach, we observe that:

  • the sum of all hash[i] is always >=0;
  • count is the sum of all positive hash[i];
  • therefore, every hash[i] is zero if and only if count is 0.

The genius of this approach is that the code is shorter, compared to our instinctive approach of maintaining the count of hash[i]==0.

所以这里的一个技巧是:用一个int count来判定当前的substring是一个anagram,而不用不停地每次loop -through hash[i]来判断是否是anagram。

然后主要注意的点是:什么时候count 变化,什么时候不变;什么时候hash变化,什么时候不变:

  • 对于每一个char,hash都应该变
  • 只有当加入的新的字符hash>0的时候,count + 1;只有当左边丢掉的字符hash >=0的时候,count – 1.

 

 public class Solution {
 public List<Integer> findAnagrams(String s, String p) {
 List<Integer> ans = new ArrayList<Integer>();
 if (s == null || s.length() == 0 || s.length() < p.length()){
 return ans;
 }
 
 int l = p.length();
 int[] hash = new int[256]; //如果都是lowercase的字母的话那么就可以直接int[26]了
 for (int i = 0; i < l; i ++){ //初始化hash
 hash[p.charAt(i)] ++;
 } 
 int right = 0; //substring的最后一个字符
 int left = 0;//substring的第一个字符
 int count = l;
 while (right < s.length()){
 char c = s.charAt(right);
 if (hash[c] > 0){ //当hash中c的值>0时,说明在p中还有多个c没有在substring中出现,
现在找到了一个
 count --; //还需要match的字符数-1 
 } 
 hash[c] --; //不论hash[c]的值,substring中出现一次c,hash[c]就一定要-1 
 if (right - left + 1 == l){ //如果现在substring的长度是和p相等的,
    if (count == 0){ //如果还需要match的字符数为0,说明所有p中的字符都在substring中match了
当前的substring就是p的一个anagram,所以把它的第一个字符的index放到ans里。
     ans.add(left);
     }
//如果现在substring的长度是和p相等的,那么下一次的loop(right+1),就会把最左边的字符给扔掉
 if (hash[s.charAt(left)] >= 0){ //如果hash[i]小于零的话,说明最左的这个字符已经多取了,
这里sliding window向右移,这个字符被扔掉也没有什么影响。所以只有当hash[i]>=0的时候,sliding
window丢掉的这个最左字符会是p中的需要的一个,此时扔掉了,count 需要 +1.
 count ++;
 }
 hash[s.charAt(left)] ++; //对于扔掉的char任何情况下都要对hash进行处理,来中和之前对他的+
 left ++; //右移window
 } 
 right ++; //右移window 
 }
 return ans;
 }
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: