本文主要是介绍【算法每日一练及解题思路】找出模式匹配字符串的异位词在原始字符串中出现的索引下标，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【算法每日一练及解题思路】找出模式匹配字符串的异位词在原始字符串中出现的索引下标
一、题目：找出模式匹配字符串的异位词在原始字符串中出现的索引下标
二、举例：
两个字符串原始字符串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;}
}
六、结果
这篇关于【算法每日一练及解题思路】找出模式匹配字符串的异位词在原始字符串中出现的索引下标的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
