跳至主要內容

判断字符串排列

linwu大约 2 分钟

判断字符串排列

给定两个字符串s1s2,判断s2是否包含s1的任意排列。如果是,返回true;否则,返回false

示例:

输入:s1 = "ab",s2 = "eidbaooo" 输出:true 解释:s2 包含 s1 的一个排列("ba")。

输入:s1 = "ab",s2 = "eidboaoo" 输出:false 解释:s2 并不包含 s1 的任意排列。

题目分析与解题步骤:

这个问题可以使用滑动窗口算法来解决。我们可以维护一个窗口,大小等于s1的长度,在s2上滑动窗口,并比较窗口内的字符是否与s1中的字符构成相同的排列。

解题步骤如下:

  1. 初始化两个计数器对象counter1counter2,用于记录s1和当前窗口内字符的出现次数。

  2. 遍历字符串s1,并统计每个字符的出现次数,存储在counter1中。

  3. 初始化两个指针leftright,分别指向窗口的左右边界。

  4. s2上使用滑动窗口,开始从左向右滑动窗口。

  5. 在每次滑动窗口时,更新窗口内字符的出现次数counter2。同时,比较counter1counter2是否相等,如果相等,表示当前窗口内的字符与s1中的字符构成相同的排列。

  6. 如果相等,返回true

  7. 如果不相等,继续滑动窗口,即将窗口的左边界向右移动一位,并更新counter2

  8. 重复步骤5-7,直到窗口滑动到s2的末尾。

  9. 如果未找到符合条件的排列,返回false

JavaScript解题框架:

function checkInclusion(s1, s2) {
    let counter1 = {};
    let counter2 = {};

    // 统计 s1 中字符的出现次数
    for (let char of s1) {
        counter1[char] = (counter1[char] || 0) + 1;
    }

    let left = 0;
    let right = 0;

    while (right < s2.length) {
        // 扩大窗口
        let char = s2[right];
        counter2[char] = (counter2[char] || 0) + 1;

        // 检查窗口内字符的出现次数是否与 s1 相同
        if (right - left + 1 === s1.length) {
            if (compareCounters(counter1, counter2)) {
                return true;
            }
            // 缩小窗口
            char = s2[left];
            counter2[char]--;
            if (counter2[char] === 0) {
                delete counter2[char];
            }
            left++;
        }

        right++;
    }

    return false;
}

// 比较两个计数器对象的键值对是否相等
function compareCounters(counter1, counter2) {
    for (let key in counter1) {
        if (counter1[key] !== counter2[key]) {
            return false;
        }
    }
    return true;
}

在这个框架中,我们使用了两个计数器对象counter1counter2,分别用于统计s1和窗口内字符的出现次数。

我们首先遍历s1,统计每个字符的出现次数,存储在counter1中。然后,使用滑动窗口在s2上进行匹配。在每次滑动窗口时,我们将当前字符的出现次数添加到counter2中,并与counter1进行比较。如果两个计数器对象的键值对相等,则表示当前窗口内的字符与s1中的字符构成相同的排列。

最后,如果找到符合条件的排列,返回true;否则,返回false

关注公众号

和小伙伴们一起学习

加入技术交流群

扫描二维码 备注加群