NC28 最小覆盖子串

https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac (opens new window)

描述

给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。

注意：

如果 s 中没有包含 t 中所有字符的子串，返回空字符串 “”；

满足条件的子串可能有很多，但是题目保证满足条件的最短的子串唯一。

示例1

输入：
"XDOYEZODEYXNZ","XYZ"

返回值：
"YXNZ"

示例2

输入：
"abcAbA","AA"

返回值：
"AbA"

解答

/**
  * 
  * @param S string字符串 
  * @param T string字符串 
  * @return string字符串
  */
function minWindow( S ,  T ) {
    const str = S;
    const target = T;
    const len = str.length;

    if (len === 0) {
        return '';
    }

    let minSub = '';
    const targetLen = target.length;

    if (targetLen === 0) {
        return '';
    }

    for (let i = 0; i < len; i++) {
        if (!target.includes(str[i])) {
            continue;
        }

        const sub = helper(str.slice(i), target);

        if (sub === '') {
            continue;
        }

        if (!minSub) {
            minSub = sub;
            continue;
        }

        if (sub.length < minSub.length) {
            minSub = sub;
        }
    }

    return minSub;
}

function helper(str, target) {
    const left = 0;
    let right = 0;
    
    const len = str.length;

    for (; right < len; right++) {
        const char = str[right];
        const index = target.indexOf(char);

        if (index !== -1) {
            target = target.replace(char, '');

            if (target.length === 0) {
                break;
            }
        }

    }

    if (target.length === 0) {
        return str.slice(left, right + 1);
    }

    return '';
}

module.exports = {
    minWindow : minWindow
};