438.Find-All-Anagrams-in-a-String

438. Find All Anagrams in a String

题目地址

https://leetcode.com/problems/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".

代码

Approach #1 Sliding Window with HashMap

Complexity Analysis

• Time complexity: O(Ns+Np) since it's one pass along both strings.

• Space complexity: O(1), because pCount and sCount contain not more than 26 elements.

class Solution {
  public List<Integer> findAnagrams(String s, String p) {
    int ns = s.length(), np = p.length();
    if (ns < np) return new ArrayList();

    Map<Character, Integer> pCount = new HashMap();
    Map<Character, Integer> sCount = new HashMap();
    // build reference hashmap using string p
    for (char ch : p.toCharArray()) {
      if (pCount.containsKey(ch)) {
        pCount.put(ch, pCount.get(ch) + 1);
      }
      else {
        pCount.put(ch, 1);
      }
    }

    List<Integer> output = new ArrayList();
    // sliding window on the string s
    for (int i = 0; i < ns; ++i) {
      // add one more letter 
      // on the right side of the window
      char ch = s.charAt(i);
      if (sCount.containsKey(ch)) {
        sCount.put(ch, sCount.get(ch) + 1);
      }
      else {
        sCount.put(ch, 1);
      }
      // remove one letter 
      // from the left side of the window
      if (i >= np) {
        ch = s.charAt(i - np);
        if (sCount.get(ch) == 1) {
          sCount.remove(ch);
        }
        else {
          sCount.put(ch, sCount.get(ch) - 1);
        }
      }
      // compare hashmap in the sliding window
      // with the reference hashmap
      if (pCount.equals(sCount)) {
        output.add(i - np + 1);
      }
    }
    return output;
  }
}

Approach #2 Sliding Windwo with Array

class Solution {
  public List<Integer> findAnagrams(String s, String p) {
    int ns = s.length(), np = p.length();
    if (ns < np)     return new ArrayList();

    int[] pCount = new int[26];
    int[] sCount = new int[26];
    for (char ch: p.toCharArray()) {
      int index = ch - 'a';
      pCount[index]++;
    }

    List<Integer> output = new ArrayList();
    for (int i = 0; i < ns; i++) {
      int index = s.charAt(i) - 'a';
      aCount[index]++;
      if (i >= np) {
        index = s.charAt(i - np) - 'a';
        aCount[index]++;
      }

      if (Arrays.equals(pCount, sCount)) {
        output.add(i - np + 1);
      }
    }

    return output;
  }
}