寻找所有异构字符串

问题描述

对于一个字符串s，给定一个字符串p，找到s中所有和p同分异构（字母的种类和数量相同，但组合可以不同）的字符串，输出他们的起始下标。

解决方法

问题解决的核心在于统计每一个字符串中字符的频率，如果两者相等，则说明是要寻找的字符串。一种方式是创建两个哈希表，其中一个存储字符串p中字符的频率，然后遍历s中和p字符串长度相同的子字符串，并采取类似队列进出的方式计算它们的频率（前一个子字符串扔掉最后一个字符在加上前面一个字符就得到新的字符串），比较该值和p，如果相同则得到一个解。但是该算法的时间复杂度为两个字符串长度的乘积，因此一般会比较慢。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        
        Map<Character, Integer> map = new HashMap<>();
        for(char ch : p.toCharArray()){
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        List<Integer> ans = new ArrayList<>();
        if(s.length() < p.length()){
            return ans;
        }
        
        Map<Character, Integer> cp = new HashMap<>();
        for(int i = 0; i < p.length() - 1; i++){
            char ch = s.charAt(i);
            cp.put(ch, cp.getOrDefault(ch, 0) + 1);
        }
        for(int i = p.length() - 1; i < s.length(); i++){
            char ch = s.charAt(i);
            cp.put(ch, cp.getOrDefault(ch, 0) + 1);
            if(cp.size() == map.size()){
                boolean flag = true;
                for(Map.Entry<Character, Integer> entry : map.entrySet()){
                    char key = entry.getKey();
                    if(!entry.getValue().equals(cp.getOrDefault(key, -1))){
                        flag = false;
                        break;
                    }
                }
                if(flag)ans.add(i + 1 - p.length());
            }
            char head = s.charAt(i + 1 - p.length());
            if(cp.get(head).equals(1)){
                cp.remove(head);
            }
            else cp.replace(head, cp.get(head) - 1);
        }
        return ans;
    }
}

更好的方法是采用类似滑动窗口的方法：

依然使用一个哈希表来存储p中字符串的频率，再初始化begin和end两个指针，这是我们把哈希表中的内容当做是begin,end之间的字符串还欠缺的值，所求的解应该满足一下条件：

1. 包含p中的所有字符
2. 每个字符的值都相等
3. 两者的长度相等

因此，可以先移动end指针，每找到一个符合条件的字符，就在哈希表中减去一个该字符，说明这个字符的需求少了一个，直到哈希表中的字符个数都小于等于0，说明当前begin,end字符串的字符集合包含p的字符集合，这时移动begin，表示抛弃掉多余的字符，如果抛弃的这个字符是我们需要的，则需要继续移动end来添加，否则当begin，end字符串的长度等于p的长度时，说明该字符串的字符集包含p的字符集并且两个集合的大小相等，这正是两个者相等的条件，得到一个解。以此类推，当end遍历完s时输出所有解。

public class Solution {
    public List<Integer> findAnagrams(String s, String t) {
        List<Integer> result = new LinkedList<>();
        if(t.length()> s.length()) return result;
        Map<Character, Integer> map = new HashMap<>();
        for(char c : t.toCharArray()){
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int counter = map.size();
        
        int begin = 0, end = 0;
        int head = 0;
        int len = Integer.MAX_VALUE;
        
        
        while(end < s.length()){
            char c = s.charAt(end);
            if( map.containsKey(c) ){
                map.put(c, map.get(c)-1);
                if(map.get(c) == 0) counter--;
            }
            end++;
            
            while(counter == 0){
                char tempc = s.charAt(begin);
                if(map.containsKey(tempc)){
                    map.put(tempc, map.get(tempc) + 1);
                    if(map.get(tempc) > 0){
                        counter++;
                    }
                }
                if(end-begin == t.length()){
                    result.add(begin);
                }
                begin++;
            }
            
        }
        return result;
    }
}