美团前端笔试8.27（求思路~）

美团编程两题，比8.13难

第一题：匹配字符串（70%+）

本来想用正则的，后来发现正则不是一个好办法，后面用了遍历分割字符串再进行判断，不知道为什么只过了70%+，应该是题目有部分理解错了

function fn(S, s, n, m) {
    let count = 0;

    for (let i = 0; i <= n - m; i++) {
        let temp = S.slice(i, i+m);
        console.log('t', temp)
        if (isValid(temp, s)) {
            console.log(temp)
            count++;
        }
    }

    return count;

}
function isValid(S, s) {
    let index = 0;
    while (index < S.length) {
        if (S[index] === s[index] || s[index] === '*') {
            index++;
        } else {
            return false;
        }
    }

    return true;
}

第二题：裁缝（60%）

我用的全排列，过了60%

function fn(n, m , S, lens, strs) {
    let sum = lens.reduce((p, v) => p + v, 0);
    if (sum !== n) return 0;

    let res = totalSort(strs);

    let count = 0;

    for (let item of res) {
        if (item.join('') === S) {
            count++;
        } else {
            continue;
        }
    }

    return count;

    // 全排列
    function totalSort(strs) {
        let res = [];
        let visited = new Array(m).fill(false);
        dfs([], 0);
        return res;
        function dfs(path, index) {
            if (path.length === m) {
                res.push([...path]);
                return;
            }


            for (let i = 0; i < strs.length; i++) {
                if (visited[i] || (i > 0 && strs[i] === strs[i-1] && !visited[i-1])) continue;

                path.push(strs[i]);
                visited[i] = true;
                dfs(path, index+1);
                visited[i] = false;
                path.pop();
            }
        }
    }
}