华为OD机试 - 关联子串 - 滑动窗口（Java 2023 B卷 100分）

在这里插入图片描述

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

给定两个字符串str1和str2，str1进行排列组合只要有一个为str2的子串则认为str1是str2的关联子串，请返回子串在str2的起始位置，若不是关联子串则返回-1。

二、输入描述

vaa nezhajava

三、输出描述

四、解题思路

读取输入的两个字符串str1和str2；
获取str1和str2的长度，分别赋值给变量a和b；
初始化变量index为-1，用于记录关联子串在str2中的起始位置；
使用一个循环，从0遍历到b-a，表示在str2中可能存在关联子串的起始位置；
在每次循环中，通过str2的substring方法截取长度为a的子串，从当前位置i开始截取；
调用check方法判断截取得到的子串是否为关联子串。如果是关联子串，将当前位置i赋值给index，并跳出循环；
输出index的值，即关联子串在str2中的起始位置。如果没有找到关联子串，则输出-1。

该算法使用滑动窗口的思想，通过遍历str2中的每个可能的起始位置，将长度为a的子串与str1进行比较，判断是否为关联子串。

在check方法中，使用两个嵌套循环，分别遍历str1和截取得到的子串的字符，通过比较字符是否相等来判断是否为关联子串。

算法的时间复杂度为O((b-a) * a)，其中a为str1的长度，b为str2的长度。在最坏情况下，需要遍历所有可能的起始位置，并对每个位置的子串进行比较。

五、Java算法源码

public static void main(String[] args) {Scanner sc = new Scanner(System.in);String[] arr = sc.nextLine().split(" ");String str1 = arr[0];String str2 = arr[1];int a = str1.length();int b = str2.length();// 记录关联子串在str2中的起始位置int index = -1;// 在str2中可能存在关联子串的起始位置for (int i = 0; i <= b - a; i++) {// 如果是关联子串，将当前位置i赋值给index，并跳出循环if (check(str1, str2.substring(i, i + a))) {index = i;break;}}System.out.println(index);
}// 判断截取得到的子串是否为关联子串
public static boolean check(String a, String b) {int count = 0;int l = a.length();List<Character> list = new ArrayList<>();for (int i = 0; i < l; i++) {list.add(b.charAt(i));}for (int i = 0; i < l; i++) {for (int j = 0; j < list.size(); j++) {if (a.charAt(i) == list.get(j)) {list.remove(j);count++;break;}}}return count == l;
}