LeetCode Note Java 00438：Find All Anagrams in a String

找出 s 字串中所有目標字串 p 的 Anagram (由相同字母池組成的單字)，返回以每個 Anagram 的開頭索引組成的 Array。

題目

Find All Anagrams in a String Medium

Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

我的解法

列出需求：

• 回傳的 List
• 判斷 Anagram 的方法
• 切出特定 String 長度的方法

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
      List<Integer> output = new ArrayList<>();
      int pAdd = p.length(); // 注意
      for (int i = 0; i < s.length() - p.length() + 1; i++) { // 注意
        String tester = s.substring(i, i + pAdd); // 注意
        if (isAnagram(tester, p)) {
          output.add(i);
        }
      }
      return output;
    }

    private boolean isAnagram(String a, String b) {
      char[] aca = a.toCharArray();
      char[] bca = b.toCharArray();
      Arrays.sort(aca);
      Arrays.sort(bca);
      return (new String(aca)).equals(new String(bca));
    }
}

結果超過時間限制。

重新嘗試：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
      List<Integer> output = new ArrayList<>();
      int pAdd = p.length(); // 注意
      for (int i = 0; i < s.length() - p.length() + 1; i++) { // 注意
        String tester = s.substring(i, i + pAdd); // 注意
        if (isAnagram(tester, p)) {
          output.add(i);
        }
      }
      return output;
    }

    private boolean isAnagram(String a, String b) {
        int[] chars = new int[26];
        for (int i = 0; i < a.length(); i++) {
            chars[a.charAt(i) - 'a']++;
        }
        for (int i = 0; i < b.length(); i++) {
            chars[b.charAt(i) - 'a']--;
        }
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

這次就通過了，但運算時間還是太久…

上面兩次嘗試只差在判斷 Anagram 的方式不同，兩種方法都是 00242：Valid Anagram 中使用的。

檢討

找了一個運算時間算快的版本來研究：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // 比較用的 array
        int freq1[] = new int[26];
        int freq2[] = new int[26];
        // 結果 list
        List<Integer> list = new ArrayList<>();
    
        if(s.length()<p.length())
            return list;
        
        // 填充比較用的 array
        for(int i=0; i<p.length(); i++){
            freq1[s.charAt(i)-'a']++;
            freq2[p.charAt(i)-'a']++;
        }
 
        int start=0;
        int end=p.length();

        // 比較第一組
        if(Arrays.equals(freq1,freq2))
            list.add(start);
    
        while(end<s.length()){
            // 去掉前一組的第一個的計數
            freq1[s.charAt(start)-'a']--;
            // 加上下一組的最後一個的計數
            freq1[s.charAt(end)-'a']++;
            // 比較
            if(Arrays.equals(freq1,freq2))
                list.add(start+1);
        
            start++;
            end++;
        }
        return list; 
    }
}

使用固定一組 Array 來滾動調整比較省時間的樣子。

參考資料

Simple Sliding Window Java Solution, O(n), (6ms, 90% beat)