Find All Anagrams in a String

Leave a comment

November 6, 2016 by oneOokay

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

 

首先对p的每个char进行hash计数看每一个char有多少个.

然后开始遍历s:

  • 一个right指针开始遍历,left指针停在开始.
  • 当当前的left和right之间的substring valid的时候, 求得一个结果.
  • 把left指针往右移. 对每一次移动进行是否valid的判断.
    • 仍旧valid的话继续把新的left和right之间的substring加入到结果.
    • 如果不valid,停止移动left,开始移动right直到下一次valid

那么这个点在于如何什么时候对hash[i]的值进行变化?怎么变?怎么判断当前的hash是否valid?

如果新建一个hash来与p的hash相比的话, 那么对于新建的这个hash, 移right的时候hash[right] ++; 移left的时候hash[left] –; 每移动任何一个指针都对两个hash进行遍历,看每一位的hash值是否一样,如果一样则valid.

以上是比较容易想到的.下面是更加简洁的: 用一个sum来表示是否valid. SLIDING WINDOW

首先并不新建另一个hash,直接在p的hash上进行操作. 由此: 只有当p的hash的所有的值都为0的时候,当前的substring才是valid.

  • 用一个count的值来check是否valid: count == 0: valid
    • count表示:还需要多少个char来组成一个p的anagram
  • 把一个char加入到当前的substring里面时, 它的hash应该是-1.
  • 当把一个char从当前的substring里移出, 它的hash应该是+1.
  • 那么hash的数值就表示:
    • hash == 0: 当前的substring里面的c的数量是刚好等于p里面c 的个数的
    • hash < 0: 当前substring里面c的数量 > p里面c的个数 (多余了,可以移除一些c没关系)
    • hash > 0: 当前substring里面c的数量 < p里面c的个数(不足,还需要更多c)
  • 当移动right, 把当前的c加入substring的时候:
    • 对加入c之前c的hash进行判断: 如果hash是>0, 则count –. c刚好是需要的.
    • 对c的hash – 1.
  • 当移动left, 一个c要从substring里面移出去时:
    • 先对c的hash进行判断:如果hash是>=0,说明将要移除的这个c是在anagram里面需要的, 将要移除了,以后还需要c来组成anagram,所以coung ++
    • 对c的hash + 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;
 }
}

另一个类似的题目是:

寻找最短的sub sequence contains 所有的tag

input 大概是这样
tag_list = [“made”,”in”,”china”]
all_tags = [“made”, “a”,”b”,”c”,”in”, “china”,”made”,”b”,”c”,”d”]

也是用这个类似的方法.

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s

%d bloggers like this: