LeetCode438.找到字符串中所有字母异位词——java

题目描述：

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = “cbaebabacd”, p = “abc” 输出: [0,6] 解释: 起始索引等于 0 的子串是 “cba”, 它是
“abc” 的异位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。 示例 2:

输入: s = “abab”, p = “ab” 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 “ab”, 它是 “ab”
的异位词。 起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。 起始索引等于 2 的子串是 “ab”, 它是 “ab”
的异位词。

第一个方法：滑动窗口
建立数组记录p字符出现的次数，一个数组记录s字符以p字符长度为单位的字符出现的次数。
窗口移动的规律：
窗口初始化状态：

随后窗口的移动状态：

此时bc的字符在数组已经记录了，故删首增尾进能实现窗口的移动。

class Solution {public List<Integer> findAnagrams(String s, String p) {if(s.length()<p.length()){return new  ArrayList<Integer>();}List<Integer> ans=new ArrayList<Integer>();int [] pcount=new int [26];int [] scount=new int[26];for(int i=0;i<p.length();i++){	//记录第一组p长度的字符是否符合条件scount[s.charAt(i)-'a']++;pcount[p.charAt(i)-'a']++;}if(Arrays.equals(scount,pcount)){ans.add(0);}for(int i=0;i<s.length()-p.length();i++){	//将第一组的第一个字符数量减去scount[s.charAt(i)-'a']--;//将窗口移动到第二组的最后一个字符的位置scount[s.charAt(i+p.length())-'a']++;if(Arrays.equals(scount,pcount)){ans.add(i+1);}}return ans;}
}

第二个方法：暴力法

class Solution {public List<Integer> findAnagrams(String s, String p) {if(s.length()<p.length()){return new ArrayList<Integer>();}List<Integer> ans=new ArrayList<Integer>();char [] pch=p.toCharArray();Arrays.sort(pch);for(int i=0;i<=s.length()-p.length();i++){char [] sch=s.substring(i,i+p.length()).toCharArray();Arrays.sort(sch);if(String.valueOf(sch).equals(String.valueOf(pch))){ans.add(i);}}return ans;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！