华为Od必看系列
华为OD机试 全流程解析+经验分享,题型分享,防作弊指南华为od机试，独家整理 已参加机试人员的实战技巧华为od 2023 | 什么是华为od，od 薪资待遇，od机试题清单华为OD机试真题大全，用 Python 解华为机试题 | 机试宝典
本篇题目：关联子串
题目
给定两个字符串str1和str2，如果字符串str1中的字符，经过排列组合后的字符串中 只要有一个是str2的子串，则认为str1是str2的关联子串 若不是关联子串则返回-1
示例一： 输入： str1="abc",str2="efghicaibii" 输出： -1 预制条件：
输入的字符串只包含小写字母两个字符串的长度范围1 ~ 100000若str2中有多个str1的组合子串，请返回第一个子串的起始位置
备注：输入字符串只包含小写，长度 1~100000
输入
输入两个字符串，分别为题目中描述的str1和str2
输出
如果str1是str2的关联子串，则返回子串在str2中的起始位置 如果不是则返回-1 若str2中有多个str1的组合子串， 请返回最小的起始位置
示例一
输入
abc efghicabiii
输出
5
说明
str2包含str1的一种排列组合(cab) 其在str2的起始位置为5(从0开始计数)
示例二
输入
abc efghicaibii
输出
-1
说明
abc字符串中三个字母的各种组合 (abc,acb,bac,bca,cab,cba),str2中均不包含因此返回-1
代码编写说明
下述代码实现了一个字符串匹配的功能，输入两个字符串 sourceString 和 targetString，找到 sourceString 的一个排列，使得 targetString 中包含该排列的起始下标最小，如果找不到则返回-1。
代码的实现逻辑是通过递归实现的，每次递归都会将当前字符串 currentString 和剩余字符串 remainingString 传入，然后枚举 remainingString 中的每个字符，将其加入 currentString 中，然后将其从 remainingString 中删除，再递归调用 find 函数，直到 remainingString 为空。如果此时 currentString 是 sourceString 的一个排列，则计算其在 targetString 中的起始下标，如果比之前的最小值还小，则更新最小值。最后返回最小值即可。
需要注意的是，这段代码的时间复杂度是 O(n!)，因为它枚举了 sourceString 的所有排列，所以在实际使用中需要谨慎。
Code
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
String inputString = scanner.nextLine();
String[] inputStrings = inputString.split(" ");
String sourceString = inputStrings[0];
String targetString = inputStrings[1];
int index = find("", new StringBuilder(sourceString), targetString);
System.out.print(index);
}
}
private static int find(String currentString, StringBuilder remainingString, String targetString) {
if (remainingString.length() == 0) {
int index = targetString.indexOf(currentString);
if (index != -1) {
return index;
}
}
int minIndex = Integer.MAX_VALUE;
for (int i = 0; i < remainingString.length(); ++i) {
StringBuilder tmp = new StringBuilder(remainingString);
int index = find(currentString + tmp.charAt(i), tmp.deleteCharAt(i), targetString);
if (index != -1) {
minIndex = Math.min(index, minIndex);
}
}
return minIndex == Integer.MAX_VALUE ? -1 : minIndex;
}
}
使用说明
参加华为od机试，一定要注意不要完全背诵代码，需要理解之后模仿写出，通过率才会高。
华为 OD 清单查看地址：https://blog.csdn.net/hihell/category_12201821.html
华为OD详细说明：https://dream.blog.csdn.net/article/details/128980730
华为OD机试题
本篇题目：关联子串题目输入输出示例一输入输出说明
示例二输入输出说明
代码编写说明Code
全网 6000+人正在学习的 爬虫专栏
⭐️ Python 爬虫 120，点击订购 ⭐️⭐️ 爬虫 100 例教程，点击订购 ⭐️
发表评论