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

该专栏题目包含两部分：
100 分值部分题目
200 分值部分题目
所有题目都会陆续更新，订阅防丢失

题目描述：

给定两个字符串str1和str2，如果字符串str1中的字符，经过排列组合后的字符串中，只要有一个字符串是str2的子串，则认为str1是str2的关联子串。

若str1是str2的关联子串，请返回子串在str2的起始位置；
若不是关联子串，则返回-1。

条件：

• 输入的字符串只包含小写字母；
• 两个字符串的长度范围[1, 100,000]之间
• 若str2中有多个str1的组合子串，请返回第一个子串的起始位置。

输入描述

输入两个字符串，分别为题目中描述的str1、str2。

输出描述

如果str1是str2的关联子串，则返回子串在str2中的起始位置。

如果str1不是str2的关联子串，则返回-1。

若str2中有多个str1的组合子串，请返回最小的起始位置。

示例

输入：

abc efghicabiii

输出：

5

说明：

str2包含str1的一种排列组合（“cab”)，此组合在str2的字符串起始位置为5（从0开始计数）

示例2

输入：

abc efghicaibii

输出：

-1

说明：
“abc”字符串中三个字母的各种组合（abc、acb、bac、bca、cab、cba），str2中均不包含，因此返回-1

题解

思路一：对str1字符串排序，对于str2 用滑动窗口遍历，比较排序后的字符串是否相等
思路二：记录str1每个字符出现的次数，对于str2 用滑动窗口遍历，比较每个字符出现的次数是否相等

源码

import java.util.Arrays;public class SubString {static Input input ;static {input = new Input("abc efghicaibii");input = new Input("abc efghicabiii");}public static void main(String[] args) {String[] ss = input.nextLine().split(" ");char[] charArray = ss[0].toCharArray();Arrays.sort(charArray);String str = new String(charArray);String tar = ss[1];int left = 0;int right = left + str.length();while (right <= tar.length()) {char[] ar = tar.substring(left, right).toCharArray();Arrays.sort(ar);if (new String(ar).equals(str)) {System.out.println(left);return;}left++;right++;}System.out.println(-1);}
}