Question

Solution

题目大意：给两个字符串，s和p，求p在s中出现的位置，p串中的字符无序，ab=ba

思路：起初想的是求p的全排列，保存到set中，遍历s，如果在set中出现，s中的第一个字符位置保存到结果中，最后返回结果。这种思路执行超时。可能是求全排列超时的。

思路2：先把p中的字符及字符出现的次数统计出来保存到map中，再遍历s，这个思路和中提到的创新解法类似

Java实现：

public List
    
      findAnagrams(String s, String p) {    List
     
       ans = new ArrayList<>();    if (s.length() <= p.length()) return ans;    // 构造map,并初始化target    Map
      
        map = new HashMap<>();    for (char tmp : p.toCharArray()) {        Bo bo = map.get(tmp);        if (bo == null) {            bo = new Bo();            map.put(tmp, bo);        }        bo.target++;    }    // 前p.length()项    for (int i = 0; i < p.length(); i++) {        char cur = s.charAt(i);        Bo bo = map.get(cur);        if (bo != null) {            bo.cur++;        }    }    if (allOne(map)) ans.add(0);    for (int i = p.length(); i < s.length(); i++) {        char cur = s.charAt(i);        if (map.get(cur) != null) map.get(cur).cur++;        char last = s.charAt(i - p.length());        if (map.get(last) != null) map.get(last).cur--;        if (allOne(map)) ans.add(i - p.length() + 1);    }    return ans;}public boolean allOne(Map
       
         map) {    for (Map.Entry
        
          entry : map.entrySet()) {        if (entry.getValue().cur != entry.getValue().target) return false;    }    return true;}class Bo {    int cur; // 当前数    int target; // 目标数    public Bo() {        this(0, 0);    }    public Bo(int cur, int target) {        this.cur = cur;        this.target = target;    }}
        
       
      
     
    

Discuss

欣赏一下别人写的，所说下面两道题用的是同一思路，记录一下

public List
    
      findAnagrams(String s, String p) {    List
     
       list = new ArrayList<>();    if (s == null || s.length() == 0 || p == null || p.length() == 0) return list;    int[] hash = new int[256]; //character hash    //record each character in p to hash    for (char c : p.toCharArray()) {        hash[c]++;    }    //two points, initialize count to p's length    int left = 0, right = 0, count = p.length();    while (right < s.length()) {        //move right everytime, if the character exists in p's hash, decrease the count        //current hash value >= 1 means the character is existing in p        if (hash[s.charAt(right++)]-- >= 1) count--;                 //when the count is down to 0, means we found the right anagram        //then add window's left to result list        if (count == 0) list.add(left);            //if we find the window's size equals to p, then we have to move left (narrow the window) to find the new match window        //++ to reset the hash because we kicked out the left        //only increase the count if the character is in p        //the count >= 0 indicate it was original in the hash, cuz it won't go below 0        if (right - left == p.length() && hash[s.charAt(left++)]++ >= 0) count++;    }    return list;}
     
    

public List
    
      findAnagrams(String s, String p) {    char[] ptrn = p.toCharArray();    char[] str = s.toCharArray();        int[] w = new int[26];        for(char c : ptrn) w[c - 'a']++;        int start = 0;                List
     
       result = new LinkedList<>();        for(int i = 0; i