华为OD机试真题 JavaScript 实现【关联子串】【2023Q1 100分】，附详细解题思路

一、题目描述

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

二、输入描述

qwe dsgfasgfwe

三、输出描述

-1

四、解题思路

1. 读取输入的两个字符串str1和str2；
2. 获取str1和str2的长度，分别赋值给变量a和b；
3. 初始化变量index为-1，用于记录关联子串在str2中的起始位置；
4. 使用一个循环，从0遍历到b-a，表示在str2中可能存在关联子串的起始位置；
5. 在每次循环中，通过str2的substring方法截取长度为a的子串，从当前位置i开始截取；
6. 调用check方法判断截取得到的子串是否为关联子串。如果是关联子串，将当前位置i赋值给index，并跳出循环；
7. 输出index的值，即关联子串在str2中的起始位置。如果没有找到关联子串，则输出-1。

该算法使用滑动窗口的思想，通过遍历str2中的每个可能的起始位置，将长度为a的子串与str1进行比较，判断是否为关联子串。

在check方法中，使用两个嵌套循环，分别遍历str1和截取得到的子串的字符，通过比较字符是否相等来判断是否为关联子串。

算法的时间复杂度为O((b-a) * a)，其中a为str1的长度，b为str2的长度。在最坏情况下，需要遍历所有可能的起始位置，并对每个位置的子串进行比较。

五、JavaScript算法源码

function calculate(str1, str2) {
    const a = str1.length;
    const b = str2.length;
    // 记录关联子串在str2中的起始位置
    let index = -1;

    // 在str2中可能存在关联子串的起始位置
    for (let i = 0; i <= b - a; i++) {
        // 如果是关联子串，将当前位置i赋值给index，并跳出循环
        if (check(str1, str2.substring(i, i + a))) {
            index = i;
            break;
        }
    }

    return index;
}

// 判断截取得到的子串是否为关联子串
function check(a, b) {
    const count = a.length;
    const list = [...b];

    for (let i = 0; i < count; i++) {
        for (let j = 0; j < list.length; j++) {
            if (a.charAt(i) === list[j]) {
                list.splice(j, 1);
                break;
            }
        }
    }

    return list.length === 0;
}

六、效果展示

这道题看似比较简单，其实还是蛮复杂的，大家一定要好好思考思考~~

1、输入

aav nezhajava

2、输出

6

3、说明

题目要求：

str1进行排列组合只要有一个为str2的子串则认为str1是str2的关联子串，输出子串在str2的起始位置。

aav排列一下变为ava，是nezhajava的关联子串，起始位置为6。

4、换个思路

虽然avaa，调整顺序可以变为aava，与nezhajava很类似，但是中间隔着一个j，故不是关联子串，输出-1。

🏆下一篇：华为OD机试真题 JavaScript 实现【相对开音节】【2022Q4 100分】，附详细解题思路

🏆本文收录于，华为OD机试（JavaScript）真题（A卷+B卷）

每一题都有详细的答题思路、详细的代码注释、样例测试，订阅后，专栏内的文章都可看，可加入华为OD刷题群（私信即可），发现新题目，随时更新，全天CSDN在线答疑。