P155 查找字符串中所有变位词

描述#

这个题目说的是，给你字符串 s 和 p，你要在 s 中找到所有 p 的变位词，并返回它们的开始下标。变位词指的是使用相同字母以不同顺序构成的单词。在这个题目中，字符串 s 和 p 都只由小写字母组成，并且长度不会超过 100。

比如说，给你的字符串 s 和 p 是：
s: bcbababac
p: abc
在字符串 s 中，abc 的变位词有 cba 和 bac，它们的组成字符都是 a/b/c，只是排列顺序不一样。
我们要返回这两个变位词的开始下标。第一个变位词的开始下标是 1，第二个变位词的开始下标是 6，因此返回：
[1，6]

代码#

public class AlgoCasts {

  private boolean equals(char[] sc, char[] pc) {
    for (int i = 0; i < sc.length; ++i)
      if (sc[i] != pc[i])
        return false;
    return true;
  }

  // Time: O(n*k), Space: O(k)
  public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (s == null || p == null || s.length() < p.length()) return result;
    int sLen = s.length(), pLen = p.length();
    char[] pc = new char[26];
    char[] sc = new char[26];
    for (int i = 0; i < pLen; ++i) {
      pc[p.charAt(i) - 'a']++;
      sc[s.charAt(i) - 'a']++;
    }

    if (equals(sc, pc)) result.add(0);
    for (int i = pLen; i < sLen; ++i) {
      sc[s.charAt(i) - 'a']++;
      sc[s.charAt(i-pLen) - 'a']--;
      if (equals(sc, pc)) result.add(i-pLen+1);
    }
    return result;
  }

  // Time: O(n), Space: O(k)
  public List<Integer> findAnagramsOn(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (s == null || p == null || s.length() < p.length()) return result;
    int sLen = s.length(), pLen = p.length();
    char[] pc = new char[26];
    for (int i = 0; i < pLen; ++i) {
      pc[p.charAt(i) - 'a']++;
    }

    int left = 0, right = 0;
    while (right < sLen) {
      if (pc[s.charAt(right) - 'a'] > 0) {
        pc[s.charAt(right) - 'a']--;
        ++right;
      } else {
        pc[s.charAt(left) - 'a']++;
        ++left;
      }
      if (right - left == pLen) result.add(left);
    }
    return result;
  }

}