成都专业的网站建设制作公司哪家好,wordpress翻译公司网站,没有网站seo怎么做,海阳seo排名优化培训“找到字符串中所有字母异位词”的难度为Medium#xff0c;看一下题目#xff1a; 给定一个字符串 S 和一个非空字符串 T#xff0c;找到 S 中所有是 T 的字母异位词的子串#xff0c;返回这些子串的起始索引。 所谓的字母异位词#xff0c;其实就是全排列#xff0c;原题… “找到字符串中所有字母异位词”的难度为Medium看一下题目 给定一个字符串 S 和一个非空字符串 T找到 S 中所有是 T 的字母异位词的子串返回这些子串的起始索引。 所谓的字母异位词其实就是全排列原题目相当于让你找 S 中所有 T 的排列并返回它们
的起始索引。 比如输入 S cbaebabacdT abc算法返回 [0,6]因为 S 中有两个子串 cba 和 bac 是 T 的排列它们的起始索引是0和6。 直接套模板(看专栏)写代码
package SlidingWindow;import java.util.*;// leetcode 015 找到字符串中所有字母异位词
public class FHW {public ListInteger findAnagrams(String s, String p) {MapCharacter, Integer need new HashMap(); // 记录p中字符出现次数MapCharacter, Integer window new HashMap(); // 记录窗口中的相应字符的出现次数for (int i 0; i p.length(); i) {char key p.charAt(i);need.put(key, need.getOrDefault(key, 0) 1);}int left 0, right 0, valid 0; // valid 表示窗口中满足 need 条件的字符个数ListInteger res new ArrayList();while (right s.length()) {// c 是将要移入窗口的字符char c s.charAt(right);// 右移窗口right;// 进行窗口内数据的一系列更新if (need.containsKey(c)) {window.put(c, window.getOrDefault(c, 0) 1);if (window.getOrDefault(c, 0).equals(need.getOrDefault(c, 0))) { // window[c] need[c]valid;}}/*** debug 输出的位置***/System.out.println(window:( left , right ));/*********************/// 判断左侧窗口是否要收缩while (right - left p.length()) { // window need shrink —窗口需要收缩// 当窗口符合条件时把起始索引加入 resif (valid need.size()) {res.add(left);}// d 是将要移出窗口的字符char d s.charAt(left);// 左移窗口left;// 进行窗口内数据的一系列更新if (need.containsKey(d)) {if (window.getOrDefault(d, 0).equals(need.getOrDefault(d, 0))) {valid--;}window.put(d, window.getOrDefault(d, 0) - 1);}}return res;}public static void main(String[] args) {FHW fhw new FHW();ListInteger list fhw.findAnagrams(abab,ab);System.out.println(list);}}和寻找字符串的排列一样只是找到一个合法异位词(排列)之后将起始索引加入 res 即可。
