题目描述

字符串中的所有变位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同，但排列不同的字符串。
示例 1:

  1. 输入: s = "cbaebabacd", p = "abc"
  2. 输出: [0,6]
  3. 解释:
  4. 起始索引等于 0 的子串是 "cba", 它是 "abc" 的变位词。
  5. 起始索引等于 6 的子串是 "bac", 它是 "abc" 的变位词。

示例 2:

  1. 输入: s = "abab", p = "ab"
  2. 输出: [0,1,2]
  3. 解释:
  4. 起始索引等于 0 的子串是 "ab", 它是 "ab" 的变位词。
  5. 起始索引等于 1 的子串是 "ba", 它是 "ab" 的变位词。
  6. 起始索引等于 2 的子串是 "ab", 它是 "ab" 的变位词。

提示:

  • 1 <= s.length, p.length <= 3 * 104
  • s 和 p 仅包含小写字母

    解题思路

    见剑指 Offer II 014. 字符串中的变位词

    实现代码

    1. public List<Integer> findAnagrams(String s, String p){
    2.   // m为长串长度
    3.   // s为长串，p为短串
    4.   int n = p.length(), m = s.length();
    5.   List<Integer> res = new ArrayList<>();
    6.   if(m<n){
    7.       return res;
    8.   }
    9.   int[] cnt1 = new int[26];
    10.   int[] cnt2 = new int[26];
    11.   for (int i = 0; i < n; ++i) {
    12.       ++cnt1[p.charAt(i) - 'a'];
    13.       ++cnt2[s.charAt(i) - 'a'];
    14.   }
    15.   if (Arrays.equals(cnt1, cnt2)) {
    16.       res.add(0);
    17.   }
    18.   for (int i = n; i < m; ++i) {
    19.       ++cnt2[s.charAt(i) - 'a'];
    20.       --cnt2[s.charAt(i - n) - 'a'];
    21.       if (Arrays.equals(cnt1, cnt2)) {
    22.           res.add(i - n + 1);
    23.       }
    24.   }
    25.   return res;
    26. }

    时间及空间复杂度分析

    时间复杂度：O(n+m+∣Σ∣)

    拓展思路