【华为OD-E卷 - 关联子串 100分（python、java、c++、js、c）】

题目

给定两个字符串str1和str2，如果字符串str1中的字符，经过排列组合后的字符串中，只要有一个字符串是str2的子串，则认为str1是str2的关联子串。
若str1是str2的关联子串，请返回子串在str2的起始位置；
若不是关联子串，则返回-1

输入描述

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

输出描述

• 若str1是str2的关联子串，请返回子串在str2的起始位置；

若不是关联子串，则返回-1。

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

备注

• 输入的字符串只包含小写字母； 两个字符串的长度范围[1, 100000]之间；

用例

用例一：

输入：

abc efghicbaiii

• 1

输出：

5

• 1

用例二：

输入：

abc efghiccaiii

• 1

输出：

-1

• 1

python解法

• 解题思路：
• 解题思路
  题目给定了两个字符串 str1 和 str2，要求判断 str1 是否是 str2 中的一个字母排列（即 str1 的字符可以通过重排后在 str2 中找到）。如果找到，则返回第一个符合的起始位置；如果没有找到，则返回 -1。

这个问题可以通过 滑动窗口 的方式高效解决。具体步骤如下：

长度检查：首先，如果 str1 的长度大于 str2 的长度，直接返回 -1，因为不可能有子串满足条件。

字符计数：使用两个计数数组 count1 和 count2 来分别记录 str1 和 str2 的字符频率。每个字符的频率存在一个长度为 26 的数组中（假设只包含小写字母）。对于 str1，我们记录其每个字符的频率；然后，我们用滑动窗口的方式遍历 str2，并在窗口中计算字符的频率。

滑动窗口：我们从 str2 的前 n 个字符（n 是 str1 的长度）开始，检查其字符频率是否与 str1 的字符频率相同。如果相同，则返回当前窗口的起始位置。然后，我们滑动窗口：每次窗口右移一个字符，更新窗口的字符频率，移除窗口最左边的字符并添加新的字符，继续比较两者的频率是否相同。如果相同，则返回窗口的起始位置。

结束条件：如果遍历完所有可能的窗口后都没有找到符合的子串，则返回 -1

str1, str2 = input().split()  # 输入两个字符串

# 定义一个函数来处理逻辑
def getResult():
    n, m = len(str1), len(str2)  # 获取两个字符串的长度
    if n > m:  # 如果 str1 长度大于 str2 长度，直接返回 -1
        return -1
    
    # 用于记录 str1 和 str2 中每个字符出现次数的数组
    count1 = [0] * 26  # 记录 str1 中每个字符的频率
    count2 = [0] * 26  # 记录 str2 中当前窗口中字符的频率
    
    # 计算 str1 中每个字符的频率
    for c in str1:
        count1[ord(c) - ord('a')] += 1  # 将字符 c 转换为对应的索引并增加计数
    
    # 初始化 str2 中的窗口，长度为 n
    for i in range(n):
        count2[ord(str2[i]) - ord('a')] += 1  # 统计窗口中字符的频率
    
    # 如果 str1 和 str2 的前 n 个字符频率一致，直接返回 0，表示从第 0 位开始
    if count1 == count2:
        return 0
    
    # 滑动窗口，从第 n 位开始，逐个字符滑动窗口
    for i in range(n, m):
        # 增加当前字符的计数
        count2[ord(str2[i]) - ord('a')] += 1
        # 移除窗口最左边的字符
        count2[ord(str2[i - n]) - ord('a')] -= 1
        
        # 如果此时的窗口字符频率与 str1 的频率一致，返回当前窗口的起始位置
        if count1 == count2:
            return i - n + 1
    
    # 如果遍历完所有窗口都没有找到匹配的子串，返回 -1
    return -1

# 调用函数并输出结果
print(getResult())

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41

java解法

• 解题思路
• 解题思路
  这道题的目的是在给定的字符串 str2 中找到一个子串，该子串是字符串 str1 的字母排列之一（即 str1 中字符的重排）。如果找到，返回第一个符合条件的子串的起始索引；如果找不到，返回 -1。

为了解决这个问题，我们可以使用 滑动窗口 和 字符计数 的方法。具体步骤如下：

初始化字符计数：首先计算 str1 中每个字符的频率，存储在 targetCount 数组中。然后，使用一个滑动窗口遍历 str2，在窗口中计算字符的频率，存储在 windowCount 数组中。

初始窗口匹配：首先，检查 str2 的前 n 个字符（n 是 str1 的长度）是否与 str1 的字符频率匹配。如果匹配，返回起始索引 0。

滑动窗口：将窗口从 str2 的前 n 个字符滑动到后面的字符。每次滑动窗口时，更新 windowCount，即移除窗口最左边的字符并加入窗口右边的新字符。每次更新后，检查窗口中的字符频率是否与 targetCount 匹配，如果匹配，返回当前窗口的起始位置。

结束条件：如果遍历完所有窗口仍未找到匹配的子串，返回 -1。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.next();  // 读取第一个字符串
        String str2 = scanner.next();  // 读取第二个字符串
        System.out.println(findSubstr(str1, str2));  // 输出结果
    }

    // findSubstr 方法用于找到第一个符合条件的子串
    public static int findSubstr(String str1, String str2) {
        // 创建两个数组，分别记录 str1 和滑动窗口中字符的出现次数
        int[] targetCount = new int[26];  // str1 的字符频率数组
        int[] windowCount = new int[26];  // str2 中当前窗口的字符频率数组

        // 统计 str1 中每个字符的频率
        for (char c : str1.toCharArray()) {
            targetCount[c - 'a']++;  // 将字符转为对应的索引（'a' -> 0, 'b' -> 1, ..., 'z' -> 25）
        }

        // 统计 str2 中前 n 个字符的频率，n 为 str1 的长度
        for (int i = 0; i < str1.length(); i++) {
            windowCount[str2.charAt(i) - 'a']++;  // 更新窗口字符频率
        }

        // 如果初始窗口中的字符频率已经匹配，直接返回 0（表示从第 0 位开始符合条件）
        if (matches(targetCount, windowCount)) {
            return 0;
        }

        // 从 str2 中第 n 个字符开始，滑动窗口
        for (int i = str1.length(); i < str2.length(); i++) {
            // 更新窗口，移除最左边的字符，添加新的字符
            windowCount[str2.charAt(i - str1.length()) - 'a']--;  // 移除最左边的字符
            windowCount[str2.charAt(i) - 'a']++;  // 添加新的字符

            // 检查更新后的窗口字符频率是否与 str1 的字符频率匹配
            if (matches(targetCount, windowCount)) {
                return i - str1.length() + 1;  // 返回窗口的起始位置
            }
        }

        // 如果遍历完所有窗口都没有找到匹配的子串，返回 -1
        return -1;
    }

    // matches 方法用于比较两个字符频率数组是否完全相同
    private static boolean matches(int[] targetCount, int[] windowCount) {
        for (int i = 0; i < 26; i++) {
            if (targetCount[i] != windowCount[i]) {  // 如果某个字符的频率不匹配
                return false;  // 返回 false
            }
        }
        return true;  // 所有字符频率匹配，返回 true
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58

C++解法

• 解题思路
• 解题思路
  这道题的目的是在字符串 str2 中找到一个与 str1 字符排列相同的子串（即 str1 中字符的重排）。我们可以利用 滑动窗口 和 字符计数 技巧来高效地解决此问题。具体的思路如下：

字符计数：首先统计 str1 中每个字符的频率，存储在 targetCount 数组中。接着使用滑动窗口的方法遍历 str2，统计窗口中的字符频率，并存储在 windowCount 数组中。

初始窗口匹配：首先，检查 str2 的前 n 个字符（n 为 str1 的长度）是否与 str1 的字符频率匹配。如果匹配，直接返回起始索引 0。

滑动窗口：将窗口从 str2 的前 n 个字符滑动到后面的字符。每次滑动时，更新 windowCount 数组（即移除窗口最左边的字符并加入新字符）。每次更新后，检查窗口中的字符频率是否与 str1 的频率相匹配。如果匹配，返回当前窗口的起始位置。

结束条件：如果遍历完所有窗口仍未找到匹配的子串，则返回 -1。

#include 
#include 
#include 

using namespace std;

// findSubstr 函数用于查找字符串 str2 中第一个与 str1 字母排列相同的子串
int findSubstr(const string& str1, const string& str2) {
    // targetCount 数组记录 str1 中每个字符的频率
    vector<int> targetCount(26, 0);  
    // windowCount 数组记录当前滑动窗口中每个字符的频率
    vector<int> windowCount(26, 0);

    // 统计 str1 中每个字符的频率
    for (char c : str1) {
        targetCount[c - 'a']++;  // 字符 'a' 对应下标 0, 'b' 对应下标 1, ..., 'z' 对应下标 25
    }

    // 初始化滑动窗口，统计 str2 中前 str1.length() 个字符的频率
    for (int i = 0; i < str1.length(); i++) {
        windowCount[str2[i] - 'a']++;  // 更新窗口字符频率
    }

    // 如果初始窗口的字符频率已经匹配，直接返回 0
    if (targetCount == windowCount) {
        return 0;
    }

    // 从 str2 的第 str1.length() 个字符开始滑动窗口
    for (int i = str1.length(); i < str2.length(); i++) {
        // 更新窗口：移除窗口最左边的字符，加入新字符
        windowCount[str2[i - str1.length()] - 'a']--;  // 移除最左边字符
        windowCount[str2[i] - 'a']++;  // 添加新字符

        // 检查更新后的窗口字符频率是否与 str1 的字符频率匹配
        if (targetCount == windowCount) {
            return i - str1.length() + 1;  // 返回当前窗口的起始位置
        }
    }

    // 如果没有找到符合条件的子串，返回 -1
    return -1;
}

int main() {
    string str1, str2;
    cin >> str1 >> str2;  // 读取输入的两个字符串
    cout << findSubstr(str1, str2) << endl;  // 输出结果
    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51

C解法

• 解题思路

• 解题思路
  这道题要求我们在字符串 str2 中查找是否有一个与字符串 str1 字母排列相同的子串，并返回第一个符合条件子串的起始位置。我们可以通过 滑动窗口 和 字符计数 技巧来高效地实现该功能。

步骤解析：

字符计数：

我们将 str1 中的每个字符的频率存储在 count1 数组中。
同样，我们将 str2 中当前窗口的字符频率存储在 count2 数组中。
初始窗口：

初始化滑动窗口为 str2 中的前 len1 个字符（即 str1 的长度），并将其字符频率存储在 count2 中。
滑动窗口：

从 str2 的第一个字符开始，滑动窗口每次向右移动一个字符。每移动一步：
移除窗口最左边的字符（即 s2[i-1]），并添加新的字符（即 s2[i + len1 - 1]）。
比较 count1 和 count2 是否相等，如果相等，说明当前窗口是 str1 的字母排列，返回当前窗口的起始位置。
结束条件：

如果找到了符合条件的子串，则返回其起始索引；如果遍历整个 str2 后都未找到，则返回 -1。

#include 
#include 

#define ALPHABET_SIZE 26  // 定义字母表大小，因为我们只考虑小写字母

// checkInclusion 函数用于检查 str2 中是否有子串是 str1 的字母排列
int checkInclusion(char* s1, char* s2) {
    int len1 = strlen(s1), len2 = strlen(s2);  // 获取两个字符串的长度
    if (len1 > len2) return -1;  // 如果 str1 的长度大于 str2，直接返回 -1

    int count1[ALPHABET_SIZE] = {0}, count2[ALPHABET_SIZE] = {0};  // 初始化两个字符计数数组
    // 统计 str1 和 str2 中前 len1 个字符的频率
    for (int i = 0; i < len1; i++) {
        count1[s1[i] - 'a']++;  // 将 str1 中每个字符的频率加入 count1
        count2[s2[i] - 'a']++;  // 将 str2 中前 len1 个字符的频率加入 count2
    }

    // 滑动窗口开始检查
    for (int i = 0; i <= len2 - len1; i++) {
        // 如果不是第一次循环，滑动窗口：更新 count2
        if (i > 0) {
            count2[s2[i - 1] - 'a']--;  // 移除窗口最左边的字符
            count2[s2[i + len1 - 1] - 'a']++;  // 添加新字符
        }
        // 比较当前窗口的字符频率是否与 str1 的字符频率相同
        if (memcmp(count1, count2, sizeof(count1)) == 0) {
            return i;  // 如果相同，返回当前窗口的起始位置
        }
    }

    return -1;  // 如果遍历完所有窗口仍未找到，返回 -1
}

int main() {
    char str1[100001], str2[100001];
    scanf("%s %s", str1, str2);  // 输入两个字符串
    printf("%d\n", checkInclusion(str1, str2));  // 输出结果
    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40

JS解法

• 解题思路

• 解题思路
  这道题目要求在字符串 str2 中查找是否有一个与字符串 str1 字母排列相同的子串，并返回第一个符合条件子串的起始位置。我们可以使用 滑动窗口 和 字符计数 技巧来高效地实现该功能。

思路概述：

字符计数：

通过两个字符计数数组，count1 用于统计 str1 中每个字符的频率，count2 用于统计 str2 中当前滑动窗口内每个字符的频率。
初始窗口：

初始化滑动窗口为 str2 中的前 len1 个字符（即 str1 的长度），并将其字符频率存储在 count2 数组中。
滑动窗口：

从 str2 的第一个字符开始，滑动窗口每次向右移动一个字符。每移动一步：
移除窗口最左边的字符（即 s2[i - str1.length]），并添加新的字符（即 s2[i]）。
比较 count1 和 count2 是否相等，如果相等，说明当前窗口是 str1 的字母排列，返回当前窗口的起始位置。
结束条件：

如果找到了符合条件的子串，则返回其起始索引；如果遍历整个 str2 后都未找到，则返回 -1。

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

// 监听输入行，获取用户输入
rl.on("line", (line) => {
  // 将输入的两个字符串按空格分割
  let [str1, str2] = line.split(" ");
  // 调用 findSubstring 函数并输出结果
  console.log(findSubstring(str1, str2));
});

// 主逻辑函数：查找 str2 中与 str1 字母排列相同的子串
function findSubstring(str1, str2) {
  // 初始化两个长度为 26 的数组用于记录字母的出现频率
  const count1 = Array(26).fill(0); // str1 中字符的频率
  const count2 = Array(26).fill(0); // 当前滑动窗口中字符的频率

  // 统计 str1 中每个字符的频率
  for (let i = 0; i < str1.length; i++) {
    count1[str1.charCodeAt(i) - 97]++;  // 'a' 的 ASCII 值是 97，所以使用 `charCodeAt(i) - 97` 得到字母对应的数组索引
  }

  // 统计 str2 中前 len1 个字符的频率
  for (let i = 0; i < str1.length; i++) {
    count2[str2.charCodeAt(i) - 97]++;
  }

  // 如果 str1 和 str2 的前 len1 个字符的频率相同，直接返回 0
  if (arraysEqual(count1, count2)) return 0;

  // 滑动窗口，从 str2 的第 len1 个字符开始滑动
  for (let i = str1.length; i < str2.length; i++) {
    // 移除窗口最左边的字符
    count2[str2.charCodeAt(i - str1.length) - 97]--;
    // 添加新字符到窗口
    count2[str2.charCodeAt(i) - 97]++;

    // 如果当前窗口的字符频率与 str1 相同，返回当前窗口的起始索引
    if (arraysEqual(count1, count2)) return i - str1.length + 1;
  }

  // 如果没有找到符合条件的子串，返回 -1
  return -1;
}

// 辅助函数：判断两个字符频率数组是否相等
function arraysEqual(arr1, arr2) {
  for (let i = 0; i < 26; i++) {
    if (arr1[i] !== arr2[i]) return false;  // 如果有任何位置的字符频率不同，返回 false
  }
  return true;  // 如果所有位置的字符频率相同，返回 true
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏