438. Find All Anagrams in a String 找出字元串中所有的變位詞

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".
      

這道題給了我們兩個字元串s和p，讓我們在s中找字元串p的所有變位次的位置，所謂變位次就是字元種類個數均相同但是順序可以不同的兩個詞，那麼我們肯定首先就要統計字元串p中字元出現的次數，然後從s的開頭開始，每次找p字元串長度個字元，來驗證字元個數是否相同，如果不相同出現了直接break，如果一直都相同了，則将起始位置加入結果res中，參見代碼如下：

這道題一個最重要的難點就是時間控制。另一個就是哈希表的應用。

第一次做：思想很簡單，但是結果逾時了：

用一個hashmap存起來p的中的資訊。

周遊s，然後與p對比

複雜度：O( (s.length-p.length) * p.length)  ) 類似于O(n^2)

class Solution {
    public class Count{
        int oldCount;
        int newCount;
        Count(int oldCount,int newCount){
            this.oldCount = oldCount;
            this.newCount = newCount;
        }
    }
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<Integer>();
        //把p存到一個hashtable裡面
        HashMap<Character,Count> p_hash = new HashMap<Character, Count>();
        for(int i = 0;i<p.length();i++){
            if(p_hash.containsKey(p.charAt(i))){
                int count = p_hash.get(p.charAt(i)).oldCount;
                count ++;
                p_hash.put(p.charAt(i),new Count(count,0));
            }else p_hash.put(p.charAt(i),new Count(1,0));
        }         

        for(int i= 0 ;i<=s.length()-p.length();i++){
            int j ;
            for(j = 0;j<p.length();j++){
                if(p_hash.containsKey(s.charAt(i+j))){
                    int old_count = p_hash.get(s.charAt(i+j)).oldCount;
                    int new_count = p_hash.get(s.charAt(i+j)).newCount;
                    new_count ++ ;
                    p_hash.put(s.charAt(i+j),new Count(old_count,new_count));
                    if(new_count > old_count) break;
                }else break;
            }
            if(j==p.length()) list.add(i);

            for(int k = 0;k<p.length();k++){
                int old_count = p_hash.get(p.charAt(k)).oldCount;
                p_hash.put(p.charAt(k),new Count(old_count,0));
            }

        }

        return list;
    }
}
           

不需要Count這個類，隻用一個count int值作為value就可以

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<Integer>();
        //把p存到一個hashtable裡面
        HashMap<Character,Integer> p_hash = new HashMap<Character, Integer>();
        for(int i = 0;i<p.length();i++){
            if(p_hash.containsKey(p.charAt(i))){
                int count = p_hash.get(p.charAt(i));
                count ++;
                p_hash.put(p.charAt(i),count);
            }else p_hash.put(p.charAt(i),1);
        }

        for(int i= 0 ;i<=s.length()-p.length();i++){
            int j ;
            for(j = 0;j<p.length();j++){
                if(p_hash.containsKey(s.charAt(i+j))){
                    int count = p_hash.get(s.charAt(i+j));
                    count--;
                    p_hash.put(s.charAt(i+j),count);
                    if(count<0) break;
                }else break;
            }
            if(j==p.length()) list.add(i);

            p_hash.clear();
            for(int k = 0;k<p.length();k++){
                if(p_hash.containsKey(p.charAt(k))){
                    int count = p_hash.get(p.charAt(k));
                    count ++;
                    p_hash.put(p.charAt(k),count);
                }else p_hash.put(p.charAt(k),1);
            }
        }

        return list;
    }
}
           

然後去網上查閱資料，看看别人是怎麼做的，怎麼就沒有逾時呢？

說實話，查了一堆，感覺和我的思想沒有差别啊

然後我又改了資料結構：用數組來存儲，用兩個數組

class Solution {
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<Integer>();
        //把p存到一個hashtable裡面
        int [] hash_old = new int[257];
        int [] hash_new = new int[257];
        for(int i =0;i<p.length();i++){
            hash_old[p.charAt(i)]++;
        }
        for(int i= 0 ;i<=s.length()-p.length();i++){
            for(int k =0;k<p.length();k++) {
                hash_new[p.charAt(k)] = hash_old[p.charAt(k)];
            }
            int j ;
            for(j = 0; j<p.length();j++){
                if(hash_new[s.charAt(i+j)]<=0) break;
                if(hash_new[s.charAt(i+j)] > 0) hash_new[s.charAt(i+j)]--;
            }
            if(j==p.length()) list.add(i);
        }
        return list;
    }
}