leetcode 567题

leetcode 567 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的子串。

示例1

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例2

输入：s1= "ab" s2 = "eidboaoo"
输出：false

思路

通过一个数组，先计算出左字符串中每个字符出现的频率，然后再遍历有字符串，对比两者的出现频率，通过一个 count 计数器，来判断左字符串中的所有字符是否都在右字符串中全部出现过，判断依据就是 count === 0

代码

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
function getCharCodeDistance(a, b) {
    return a.charCodeAt() - b.charCodeAt();
}

function checkInclusion(s1, s2) {
    const freq = new Array(256).fill(0);
    if (s2.length === 0 || s2.length < s1.length) {
        return false;
    }
    for (let i = 0; i < s1.length; i++) {
        freq[getCharCodeDistance(s1[i], 'a')]++;
    }
    let left = 0;
    let right = 0;
    let count = s1.length;

    while (right < s2.length) {
        if (freq[getCharCodeDistance(s2[right], 'a')] >= 1) {
            count--;
        }
        freq[getCharCodeDistance(s2[right], 'a')]--;
        right++;
        if (count === 0) {
            return true;
        }
        if (right - left === s1.length) {
            if (freq[getCharCodeDistance(s2[left], 'a')] >= 0) {
                count++;
            }
            freq[getCharCodeDistance(s2[left], 'a')]++;
            left++;
        }
    }
    return false;
}

复杂度分析:

时间复杂度: O(N)
空间复杂度：O(1)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG 科学上网工具

leetcode 567 字符串的排列

思路

代码

CATALOG

FEATURED TAGS

FRIENDS