华为OD机试真题---关联子串

华为OD机试中的“关联子串”题目是一个考察字符串处理和算法理解的经典问题。以下是对该题目的详细解析：

一、题目描述

给定两个字符串str1 和 str2，如果字符串 str1 中的字符，
经过排列组合后的字符串中只要有一个是 str2 的子串，
则认为 str1 是 str2 的关联子串，若不是关联子串则返回 -1
示例:
输入:

abc efghicaibii

输出:

-1

预制条件:
1.输入的字符串只包含小写字母
2.两个字符串的长度范围1~100000
3.若 str2 中有多个 str1 的组合子串，请返回第一个子串的起始位置
备注:输入字符串只包含小写，长度 1~100000

二、输入描述

输入两个字符串，分别为题目中描述的str1和str2。输入的字符串只包含小写字母，且两个字符串的长度范围在1到100000之间。

三、输出描述

如果str1是str2的关联子串，则返回子串在str2中的起始位置。如果不是关联子串，则返回-1。若str2中有多个str1的组合子串，则返回最小的起始位置。

四、解题思路

1. 滑动窗口与字符频率匹配：

   • 滑动窗口：用于遍历 str2 的所有可能的子串，这些子串的长度与 str1 相同。
   • 字符频率匹配：通过比较两个字符串的字符频率，可以快速判断一个字符串是否是另一个字符串的排列。这是因为排列仅仅是字符的顺序不同，而字符的数量和种类完全相同。

2. 边界条件处理：

   • 虽然题目已经规定了字符串的长度范围，并且确保两个字符串都是小写字母，但在实际编码中仍需注意输入验证。例如，输入可能包含多余的空格，或者输入的字符串不符合题目要求。
   • 特别要注意的是，当 str1 的长度大于 str2 时，直接返回 -1，因为不可能在较短的字符串中找到较长的字符串的排列。

3. 性能优化：

   • 使用数组记录字符频率而不是哈希表，是因为题目限制字符集为小写字母（共26个），这样可以节省空间并且提高访问速度。
   • 每次只遍历 str2 的必要部分（即从 0 到 len2 - len1），避免了不必要的计算。

五、示例代码（Java）

import java.util.Scanner;public class AssociatedSubstring {/*** 主函数入口* 本程序用于判断第二个字符串是否是第一个字符串的排列，并输出其起始位置* @param args 命令行参数*/public static void main(String[] args) {// 创建Scanner对象，用于读取输入Scanner sc = new Scanner(System.in);// 读取一行输入，并根据空格分割成两个字符串String[] str = sc.nextLine().split(" ");// 提取分割后的字符串数组中的第一个元素String str1 = str[0];// 提取分割后的字符串数组中的第二个元素String str2 = str[1];// 计算第一个字符串的长度int len1 = str1.length();// 计算第二个字符串的长度int len2 = str2.length();// 定义目标索引，默认为-1，表示未找到int targetIndex = -1;// 遍历第二个字符串，寻找第一个字符串的排列for (int i = 0; i <= len2 - len1; i++) {// 截取当前遍历位置开始，与第一个字符串等长的子字符串String tmp = str2.substring(i, i + len1);// 判断截取的子字符串是否是第一个字符串的排列if (isPermutation(str1, tmp)) {// 如果是排列，记录起始索引targetIndex = i;// 找到后即可退出循环break;}}// 输出目标索引System.out.println(targetIndex);}/*** 判断两个字符串是否为互为排列* 排列是指两个字符串可以通过重新排列各自的字符而相互转换* 本方法通过比较两个字符串中每个字符的频率来判断它们是否为排列* * @param s1 第一个字符串，不区分大小写* @param s2 第二个字符串，不区分大小写* @return 如果s1和s2是排列关系，则返回true；否则返回false*/private static boolean isPermutation(String s1, String s2) {// 初始化两个数组，用于统计s1和s2中每个字母的出现次数int[] count1 = new int[26];int[] count2 = new int[26];// 统计s1中每个字符的频率for (char c : s1.toCharArray()) {count1[c - 'a']++;}// 统计s2中每个字符的频率for (char c : s2.toCharArray()) {count2[c - 'a']++;}// 比较两个字符频率数组for (int i = 0; i < 26; i++) {// 如果两个数组中当前位置的计数不相等，则字符串不是排列if (count1[i] != count2[i]) {return false;}}// 所有字符频率都相等，字符串是排列return true;}
}

六、示例代码详解

• 输入处理：使用 Scanner 读取输入，并用 split 方法分割成两个字符串。这里假设输入格式严格符合题目要求，即两个字符串之间用空格分隔。
• 滑动窗口：在 for 循环中，使用 substring 方法截取 str2 的子串，子串的长度与 str1 相同。
• 字符频率匹配：isPermutation 方法通过两个长度为26的数组记录两个字符串的字符频率，并逐项比较。如果所有字符的频率都相同，则这两个字符串是排列关系。
• 结果输出：一旦找到匹配的子串，记录其起始位置并立即退出循环，因为题目要求返回第一个匹配子串的起始位置。

特殊情况处理

• 空字符串：虽然题目已经排除这种情况，但理论上，如果 str1 或 str2 为空，则可以直接返回 -1，因为空字符串不能构成任何非空字符串的排列。
• 完全相同：如果 str1 正好是 str2 的一个子串（包括顺序相同），该算法仍然有效，因为完全相同的字符串也是排列关系的一种特殊情况。

七、运行示例解析

解析步骤

1、读取输入并分割字符串

• Scanner 对象读取输入 abc efghicaibii。
• 使用 split(" ") 方法将输入按空格分割成两个字符串数组 str。
• str[0] 是 “abc”，str[1] 是 “efghicaibii”。

2、计算字符串长度

• str1 的长度 len1 是 3。
• str2 的长度 len2 是 11。

3、初始化目标索引

• targetIndex 初始化为 -1，表示未找到排列。

4、遍历 str2 寻找排列

• 循环从 i = 0 到 i = len2 - len1，即从 i = 0 到 i = 8。
• 在每次循环中，截取 str2 中从 i 开始，长度为 len1 的子字符串 tmp，并与 str1 比较是否为排列。

5、具体遍历过程

• i = 0 时，tmp = “efg”，调用 isPermutation(“abc”, “efg”) 返回 false。
• i = 1 时，tmp = “fgh”，调用 isPermutation(“abc”, “fgh”) 返回 false。
• i = 2 时，tmp = “ghi”，调用 isPermutation(“abc”, “ghi”) 返回 false。
• i = 3 时，tmp = “hic”，调用 isPermutation(“abc”, “hic”) 返回 false。
• i = 4 时，tmp = “ica”，调用 isPermutation(“abc”, “ica”) 返回 false。
• i = 5 时，tmp = “cai”，调用 isPermutation(“abc”, “cai”) 返回false。
• i = 6时，tmp = “aib”，调用 isPermutation(“abc”, “aib”) 返回false。
• i = 7 时，tmp = “ibi”，调用 isPermutation(“abc”, “ibi”) 返回false。
• i = 8 时，tmp = “bii”，调用 isPermutation(“abc”, “bii”) 返回false。

6、输出结果

• 最终输出 targetIndex，即 -1。

输出

-1

八、注意事项

1. 性能优化：由于字符串长度可能达到100000，因此需要注意算法的时间复杂度。上述代码使用了滑动窗口和字符频率匹配的方法，时间复杂度为O(n*m)，其中n为str2的长度，m为str1的长度。在大多数情况下，这种方法是高效的。
2. 边界条件：需要处理一些边界情况，如str1或str2为空字符串，或者str1的长度大于str2的长度等。这些边界情况在题目描述中通常已经明确排除。

通过以上解析和示例代码，相信你可以更好地理解并解决华为OD机试中的“关联子串”问题。