【算法每日一练及解题思路】找出模式匹配字符串的异位词在原始字符串中出现的索引下标
【算法每日一练及解题思路】找出模式匹配字符串的异位词在原始字符串中出现的索引下标
一、题目：找出模式匹配字符串的异位词在原始字符串中出现的索引下标
二、举例：
两个字符串原始字符串initStr=123sf3rtfb,模式匹配字符串regx=f3s，找到模式匹配字符串regx(regx的异位词为f3s,fs3,3fs,3sf,sf3,s3f)在原始字符串initStr的索引下标2(对应3fs)和3(对应sf3)
三、思路：
解题思路：通过滑动时间窗口在原始字符串中找出长度匹配的子串，再去跟模式匹配字符串比较判断是否为其异位词
四、总结：
通过滑动时间窗口在原始字符串中找出长度匹配的子串，再去跟模式匹配字符串比较判断是否为其异位词
五、代码
import java.util.Scanner;/* @author Dylaniou* @date 20240831* @desc 找出模式匹配字符串的异位词在原始字符串中出现的索引下标* 两个字符串原始字符串initStr=123sf3rtfb,模式匹配字符串regx=f3s，找到模式匹配字符串regx(regx的异位字符,regx的异位词为f3s,fs3,3fs,3sf,sf3,s3f)在原始字符串initStr的索引下标2(对应3fs)和3(对应sf3)*/
public class IdentifyAnagram {public static void main(String[] args) {try(Scanner scanner = new Scanner(System.in);){String str = "" ;if(!str.equals("end")){System.out.print("请输入原始字符串内容：");str = scanner.nextLine();String initStr = str;System.out.print("请输入模式匹配字符串内容：");str = scanner.nextLine();String regx = str;getAnagramIndex(initStr,regx);}}}/** 获取指定字符串对应的异位词在原始字符串中出现的下标*/public static void getAnagramIndex(String initStr,String regx){//使用滑动时间窗口，从左到右依次遍历，窗口长度达到指定字符串长度则开始比较是否为异位词，//窗口左边界应从原始字符串左侧第一个字母逐个滑动过去，//每个滑动窗口的长度均为指定字符串的长度，//当窗口右边界达到原始字符串最后一个字符则终止滑动int left = 0;int right = 0;int windowSize = regx.length();while(right < initStr.length()){if((right-left)+1 == windowSize){String tmpStr = initStr.substring(left, right+1);if(isAnagram(tmpStr, regx)){System.out.println(left+":"+tmpStr);}right = ++left;}else{right++;}}}/** 判断两个字符串是否互为异位词:两个字符串中每个字符出现的次数均相同则说明互为异位词*/public static boolean isAnagram(String a,String b){if(a.length() != b.length()){return false;}int[] charCounts = new int[256];//假设只处理数字字母的组合;for(int i = 0; i < a.length(); i++){charCounts[a.charAt(i)]++;//a字符串中某字符出现一次则对应索引下标计数加1charCounts[b.charAt(i)]--;//b字符串中某字符出现一次则对应索引下标计数减1}for(int count:charCounts){if(count!=0){//如果互为异位词则每个字符在charCounts中的索引下标的计数应该都是0(因为一加一减相互抵消了)return false;}}return true;}
}
六、结果
