题目描述
给定两个字符串str1和str2，如果字符串str1中的字符，经过排列组合后的字符串中，只要有一个字符串是str2的子串，则认为str1是str2的关联子串。
若str1是str2的关联子串，请返回子串在str2的起始位置；
若不是关联子串，则返回-1。
输入描述
输入两个字符串，分别为题目中描述的str1、str2。
输出描述
若str1是str2的关联子串，请返回子串在str2的起始位置；
若不是关联子串，则返回-1。
若str2中有多个str1的组合子串，请返回最小的起始位置。
备注
- 输入的字符串只包含小写字母；
- 两个字符串的长度范围[1, 100000]之间；
用例
| 输入 | abc efghicbaiii |
| 输出 | 5 |
| 说明 | str2包含str1的一种排列组合（"cab")，此组合在str2的字符串起始位置为5（从0开始计数） |
| 输入 | abc efghiccaiii |
| 输出 | -1 |
| 说明 | “abc”字符串中三个字母的各种组合（abc、acb、bac、bca、cab、cba），str2中均不包含，因此返回-1 |
题目解析
本题看上去是要求解全排列，但是题目描述数量级为：两个字符串的长度范围[1, 100000]之间；
因此str1的全排列肯定会超时。
本题可以使用尺取法来求解，尺取法其实就是高级一点的滑动窗口，常用于解决最小覆盖子串问题，比如
大家可以认真看下上面这个博客，对尺取法有个大致了解。
尺取法，通常是有一个子串str1，和一个父串str2，我们需要在父串str2中找到包含str1子串所有字符的目标串target，不在意字符顺序。
解决方案很固定：
预处理动作：
- 统计出子串str1中各字符的数量，记录到count中，这里的count容器通常选择128长度的数组，因为字符串中的字符通常都是ASCII码表的字符，而ASCII码只有128个，因此选择128长度的数组就可以涵盖到所有字符。
- 定义一个total变量，来记录str1字符的总数（即str1的长度）
滑窗动作：
- 初始滑窗，即父串str2的0~str1.length-1范围的滑窗。此时滑窗只有新增字符的过程，即滑窗左边界保持在0，而滑窗右边界从0运动到str1.length-1位置。
- 后续滑窗，即父串str2的 i ~ i + str1.length – 1，其中 i >= 1，每次滑窗整体向右移动一格，即相较于上一个滑窗，会失去 str2[i-1]字符，以及新增 str2[i + str1.length – 1] 字符。
滑窗的意义：
- 滑窗其实就是一个str2的子串，我们可以基于滑窗来统计滑窗内子串各字符的数量，如果滑窗内各字符的数量与str1各字符数量一致，则说明滑窗内子串就是一个目标子串
滑窗处理新增字符：
- 当滑窗新增一个字符c时，我们应该count[c] -= 1，表示滑窗子串和str1的差别缩小了，此时total是否也需要-=1吗？total是str1的字符总数，此时需要细化讨论
- 如果字符c不是str1内的字符，则total不需要-=1
- 如果字符c是str1内的字符，此时又需要细化讨论，字符c虽然是str1内的字符，但是滑窗内c字符的数量完全有可能超过str1内的字符数量，即滑窗内存在多余的字符c，那么此时滑窗新增了一个c，并不会缩小和str1的差距，即total不需要-=1。
那么此时就需要搞清楚，如何判断滑窗内字符c是否是str1的字符？以及是str1字符的情况下，是否为超标字符？
上面两个判断，可以用一句话实现：count[c] > 0
- 如果滑窗新增的字符c不是str1字符，则必然count[c] <= 0
- 如果滑窗新增的字符c是str1字符，但是超标了，则经过count[c]–动作，超过的c字符，必然count[c] <= 0
滑窗处理移除字符：
当滑窗移除一个字符c是，我们应该count[c]++，表示滑窗子串和str1的差别扩大了，此时total是否也需要+=1吗？total是str1的字符总数，此时需要细化讨论：
- 如果字符c不是str1内的字符，则total不需要+=1
- 如果字符c是str1内的字符，此时又需要细化讨论，字符c虽然是str1内的字符，但是滑窗内c字符的数量完全有可能超过str1内的字符数量，即滑窗内存在多余的字符c，那么此时滑窗移除一个c，并不会扩大和str1的差距，即不需要total+=1
那么此时就需要搞清楚，如何判断滑窗内字符c是否是str1的字符？以及是str1字符的情况下，是否为超标字符？
上面两个判断，可以用一句话实现：count[c] >= 0
- 如果滑窗移除的字符c不是str1字符，则移除之前必然count[c] < 0
- 如果滑窗移除的字符c是str1字符，但是超标了，则移除之前必然count[c] < 0
Java算法源码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.next();
String str2 = sc.next();
System.out.println(getResult(str1, str2));
}
public static int getResult(String str1, String str2) {
// count用于统计str1中各字符的数量
int[] count = new int[128];
for (int i = 0; i < str1.length(); i++) {
char c = str1.charAt(i);
count[c]++;
}
// total统计str1总共字符个数
int total = str1.length();
// 初始滑窗，滑窗范围内容，就是一个子串
for (int i = 0; i < str1.length(); i++) {
// 滑窗子串新增的字符
char add = str2.charAt(i);
// 如果新增字符是str1的字符，即count[add] > 0时，则说明滑窗子串已找到一个目标字符，此时剩余add字符数量count[add]--,剩余目标字符总数total--
if (count[add]-- > 0) {
total--;
}
}
// 如果total == 0，则说明滑窗内所有字符都是str1内的字符，由于限定了滑窗的长度就是str1的长度，因此滑窗内字符和str1完全匹配
if (total == 0) return 0;
// 下一个滑窗范围是 i ~ i + str1.length() - 1
for (int i = 1; i + str1.length() - 1 < str2.length(); i++) {
// 相较于上一个滑窗失去的字符remove
char remove = str2.charAt(i - 1);
// 相较于上一个滑窗新增的字符add
char add = str2.charAt(i + str1.length() - 1);
// 本轮滑窗remove字符，在上一轮是被add的字符，我们假设此字符为c，此时可以分两种情况讨论：
// 1、c是str1的字符，则初始统计时count[c]>0，上一轮滑窗加入c字符，则count[c]--，此轮count[c]是有可能>=0或者<0的，
// 1.1、如果本轮count[c]>=0，则说明上轮滑窗并没有找到所有的c字符，因此本轮移除的c字符可以还原total数量
//
// 1.2、如果本轮count[c]<0，这说明上轮滑窗内的c字符超标了，即c字符是目标字符，但是滑窗内包含的c字符数量超过了str1中c字符的数量，因此本轮移除c字符是超标部分，不会还原total
// 2、c不是str1的字符，则初始统计时count[c]==0，上一轮滑窗加入c字符，则count[c]--，此轮必然count[c]<0，因此c字符的移除，并不会还原total
if (count[remove]++ >= 0) {
total++;
}
if (count[add]-- > 0) {
total--;
}
if (total == 0) {
return i;
}
}
return -1;
}
}
JS算法源码
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
rl.on("line", (line) => {
let [str1, str2] = line.split(" ");
console.log(getResult(str1, str2));
});
function getResult(str1, str2) {
// count用于统计str1中各字符的数量
const count = {};
for (let i = 0; i < str1.length; i++) {
const c = str1[i];
count[c] = (count[c] ?? 0) + 1;
}
// total统计str1总共字符个数
let total = str1.length;
// 初始滑窗，滑窗范围内容，就是一个子串
for (let i = 0; i < str1.length; i++) {
// 滑窗子串新增的字符
const add = str2[i];
// 如果新增字符是str1的字符，即count[add] > 0时，则说明滑窗子串已找到一个目标字符，此时剩余add字符数量count[add]--,剩余目标字符总数total--
if (count[add]-- > 0) {
total--;
}
}
// 如果total == 0，则说明滑窗内所有字符都是str1内的字符，由于限定了滑窗的长度就是str1的长度，因此滑窗内字符和str1完全匹配
if (total == 0) return 0;
// 下一个滑窗范围是 i ~ i + str1.length() - 1
for (let i = 1; i + str1.length - 1 < str2.length; i++) {
// 相较于上一个滑窗失去的字符remove
const remove = str2[i - 1];
// 相较于上一个滑窗新增的字符add
const add = str2[i + str1.length - 1];
// 本轮滑窗remove字符，在上一轮是被add的字符，我们假设此字符为c，此时可以分两种情况讨论：
// 1、c是str1的字符，则初始统计时count[c]>0，上一轮滑窗加入c字符，则count[c]--，此轮count[c]是有可能>=0或者<0的，
// 1.1、如果本轮count[c]>=0，则说明上轮滑窗并没有找到所有的c字符，因此本轮移除的c字符可以还原total数量
// 1.2、如果本轮count[c]<0，这说明上轮滑窗内的c字符超标了，即c字符是目标字符，但是滑窗内包含的c字符数量超过了str1中c字符的数量，因此本轮移除c字符是超标部分，不会还原total
// 2、c不是str1的字符，则初始统计时count[c]==0，上一轮滑窗加入c字符，则count[c]--，此轮必然count[c]<0，因此c字符的移除，并不会还原total
if (count[remove]++ >= 0) {
total++;
}
if (count[add]-- > 0) {
total--;
}
if (total == 0) return i;
}
return -1;
}
Python算法源码
# 输入获取
str1, str2 = input().split()
# 算法入口
def getResult():
# count用于统计str1中各字符的数量
count = {}
for c in str1:
count[c] = count.get(c, 0) + 1
# total统计str1总共字符个数
total = len(str1)
# 初始滑窗，滑窗范围内容，就是一个子串
for i in range(len(str1)):
# 滑窗子串新增的字符
add = str2[i]
# 如果新增字符是str1的字符，即count[add] > 0时，则说明滑窗子串已找到一个目标字符，此时剩余add字符数量count[add]--,剩余目标字符总数total--
if count.get(add) is not None:
if count[add] > 0:
total -= 1
count[add] -= 1
# 如果total == 0，则说明滑窗内所有字符都是str1内的字符，由于限定了滑窗的长度就是str1的长度，因此滑窗内字符和str1完全匹配
if total == 0:
return 0
# 下一个滑窗范围是 i ~ i + str1.length() - 1
for i in range(1, len(str2) - len(str1) + 1):
# 相较于上一个滑窗失去的字符remove
remove = str2[i-1]
# 相较于上一个滑窗新增的字符add
add = str2[i + len(str1) - 1]
# 本轮滑窗remove字符，在上一轮是被add的字符，我们假设此字符为c：
# 1、c是str1的字符，则初始统计时count[c]>0，上一轮滑窗加入c字符，则count[c]--，此轮count[c]是有可能>=0或者<0的，
# 1.1、如果本轮count[c]>=0，则说明上轮滑窗并没有找到所有的c字符，因此本轮移除的c字符可以还原total数量
# 1.2、如果本轮count[c]<0，这说明上轮滑窗内的c字符超标了，即c字符是目标字符，但是滑窗内包含的c字符数量超过了str1中c字符的数量，因此本轮移除c字符是超标部分，不会还原total
if count.get(remove) is not None:
if count[remove] >= 0:
total += 1
count[remove] += 1
if count.get(add) is not None:
if count[add] > 0:
total -= 1
count[add] -= 1
if total == 0:
return i
return -1
# 算法调用
print(getResult())
C算法源码
#include <stdio.h>
#include <string.h>
#define MAX_LEN 100000
int getResult(char *str1, char *str2);
int main() {
char str1[MAX_LEN], str2[MAX_LEN];
scanf("%s %s", str1, str2);
printf("%dn", getResult(str1, str2));
return 0;
}
int getResult(char *str1, char *str2) {
// count用于统计str1中各字符的数量
int count[128] = {0};
for (int i = 0; i < strlen(str1); i++) {
char c = str1[i];
count[c]++;
}
// total统计str1总共字符个数
int total = strlen(str1);
// 初始滑窗，滑窗范围内容，就是一个子串
for (int i = 0; i < strlen(str1); i++) {
// 滑窗子串新增的字符
char add = str2[i];
// 如果新增字符是str1的字符，即count[add] > 0时，则说明滑窗子串已找到一个目标字符，此时剩余add字符数量count[add]--,剩余目标字符总数total--
if (count[add]-- > 0) {
total--;
}
}
// 如果total == 0，则说明滑窗内所有字符都是str1内的字符，由于限定了滑窗的长度就是str1的长度，因此滑窗内字符和str1完全匹配
if (total == 0) return 0;
// 下一个滑窗范围是 i ~ i + str1.length() - 1
for (int i = 1; i + strlen(str1) - 1 < strlen(str2); i++) {
// 相较于上一个滑窗失去的字符remove
char remove = str2[i - 1];
// 相较于上一个滑窗新增的字符add
char add = str2[i + strlen(str1) - 1];
// 本轮滑窗remove字符，在上一轮是被add的字符，我们假设此字符为c，此时可以分两种情况讨论：
// 1、c是str1的字符，则初始统计时count[c]>0，上一轮滑窗加入c字符，则count[c]--，此轮count[c]是有可能>=0或者<0的，
// 1.1、如果本轮count[c]>=0，则说明上轮滑窗并没有找到所有的c字符，因此本轮移除的c字符可以还原total数量
//
// 1.2、如果本轮count[c]<0，这说明上轮滑窗内的c字符超标了，即c字符是目标字符，但是滑窗内包含的c字符数量超过了str1中c字符的数量，因此本轮移除c字符是超标部分，不会还原total
// 2、c不是str1的字符，则初始统计时count[c]==0，上一轮滑窗加入c字符，则count[c]--，此轮必然count[c]<0，因此c字符的移除，并不会还原total
if (count[remove]++ >= 0) {
total++;
}
if (count[add]-- > 0) {
total--;
}
if (total == 0) {
return i;
}
}
return -1;
}免责声明：
1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文
评论0