用wordpress开发网站模板下载,小程序一键开发免费,发布网站需要备案吗,彩票网站为啥链接做两次跳转华为OD机试中的“关联子串”题目是一个考察字符串处理和算法理解的经典问题。以下是对该题目的详细解析#xff1a;
一、题目描述
给定两个字符串str1 和 str2#xff0c;如果字符串 str1 中的字符#xff0c; 经过排列组合后的字符串中只要有一个是 str2 的子串#xff…华为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的组合子串则返回最小的起始位置。
四、解题思路 滑动窗口与字符频率匹配 滑动窗口用于遍历 str2 的所有可能的子串这些子串的长度与 str1 相同。字符频率匹配通过比较两个字符串的字符频率可以快速判断一个字符串是否是另一个字符串的排列。这是因为排列仅仅是字符的顺序不同而字符的数量和种类完全相同。 边界条件处理 虽然题目已经规定了字符串的长度范围并且确保两个字符串都是小写字母但在实际编码中仍需注意输入验证。例如输入可能包含多余的空格或者输入的字符串不符合题目要求。特别要注意的是当 str1 的长度大于 str2 时直接返回 -1因为不可能在较短的字符串中找到较长的字符串的排列。 性能优化 使用数组记录字符频率而不是哈希表是因为题目限制字符集为小写字母共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八、注意事项
性能优化由于字符串长度可能达到100000因此需要注意算法的时间复杂度。上述代码使用了滑动窗口和字符频率匹配的方法时间复杂度为O(n*m)其中n为str2的长度m为str1的长度。在大多数情况下这种方法是高效的。边界条件需要处理一些边界情况如str1或str2为空字符串或者str1的长度大于str2的长度等。这些边界情况在题目描述中通常已经明确排除。
通过以上解析和示例代码相信你可以更好地理解并解决华为OD机试中的“关联子串”问题。
